HDU 1213 How Many Tables 并查集 寻找不同集合的个数
题目大意：有n个人 m行数据，每行数据给出两个数A B，代表A-B认识，如果A-B B-C认识则A-C认识，认识的人可以做一个桌子，问最少需要多少个桌子。
题目思路：利用并查集对相互认识的人进行集合的划分，划分完毕后进行遍历，如果发现一个点的根节点是本身，证明找到一个集合，统计集合数便是答案了。
#include<cstdio> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 1000005 using namespace std; int father[MAX]; int Find(int x) { while(x!=father[x]) { x=father[x]; } return x; } int main() { int T,i,j,a,b,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) father[i]=i; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); int x=Find(a); int y=Find(b); if(x!=y) { father[x]=y; } } int sum=0; for(i=1;i<=n;i++) { if(Find(i)==i)//如果一个点的根节点是本身，证明找到一个新的集合 sum++; } printf("%d ",sum); } return 0; }