Description

蛤瑋成為了實驗室主任,現在學校要求他建好一個機房里的通信網絡.這個網絡中有n臺主機，現在已知建設好了m條線路，可以讓一些主機直接或間接通信，為了使這n臺主機互相之間都可以直接或間接通信，請問蛤瑋最少還需建設多少條線路。 間接通信指：若A,B可以直接通信，B,C可以直接通信，則A,C可以間接通信，同理若C,D可以直接通信，A,D也可以間接通信。

Input

輸入第一行為一個整數T(1<=T<=10)，代表數據組數。對于每組數據，第一行為兩個整數n(1<=n<=100),m(1<=m<=n*n)，接下來m行每行兩個整數u,v(1<=u,v<=n)，表示主機u,v之間已建立線路。

Output

對于每組數據，輸出一個整數，表示還需建設的線路數。

Sample Input

1 3 3 1 1 2 1 1 2

Sample Output

1 AC代碼： #include <iostream> using namespace std; #define Size 110 int a[Size]; int find(int x){while(a[x]!=x)x=a[x];return x; } int merage(int x,int y){x=find(x);y=find(y);if(x!=y)a[x]=y; } int main() {int N,M,i,x,y,s;int T;while(cin>>T)while(T--){cin>>N>>M;for(i=1;i<=N;i++)a[i]=i;for(i=0;i<M;i++){cin>>x>>y;merage(x,y);}s=0;for(i=1;i<=N;i++)if(a[i]==i)s++;cout<<s-1<<endl;}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的蛤玮的机房的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。