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 <cstdio> #include <iostream> using namespace std; int pre[1001]; int find(int x) { int i = x; while(pre[i]!=i) { i = pre[i]; } int a = x,b; while(a!=i) { b = pre[a]; pre[a] = i; a = b; } return i; } int main() { int n,m,x,y; int t; scanf("%d",&t); while(t--) { scanf("%d",&n); int sum = n - 1; scanf("%d",&m); for(int i = 1; i <= n; i++) pre[i] = i; for(int i = 0; i < m; i++) { scanf("%d%d",&x,&y); int f1 = find(x); int f2 = find(y); if(f1!=f2) { pre[f1] = f2; sum--; } } printf("%d\n",sum); } return 0; }
