HDU - 1213 How Many Tables（并查集）
#include <stdio.h>
int f[1010],n,m;
//这里是初始化，非常地重要，数组里面存的是自己数组下标的编号就好了。
void init()
{
for(int i=1;i<=n;i++) f[i]=i;
}
//这是找爹的递归函数，不停地去找爹，直到找到祖宗为止，其实就是去找犯罪团伙的最高领导人，
//“擒贼先擒王”原则。
int getf(int v)
{
if(f[v]==v) return v; else {
//这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的“BOSS”改为最后找//到的祖宗编号，也就是犯罪团伙的最高领导人编号。这样可以提高今后找到犯罪团伙的//最高领导人（其实就是树的祖先）的速度。f[v]=getf(f[v]);//这里进行了路径压缩return f[v];}
} //请从此处开始阅读程序，从主函数开始阅读程序是一个好习惯。
int main()
{
int t;scanf("%d",&t);while(t--){
scanf("%d %d",&n,&m); init(); //初始化是必须的for(int i=1;i<=m;i++) {
int x,y;scanf("%d %d",&x,&y);//开始合并犯罪团伙 int t1=getf(x);//t1、t2分别为x和y的大BOSS（首领），int t2=getf(y);//每次双方的会谈都必须是各自最高领导人才行if(t1!=t2) f[t2]=t1;//判断两个结点是否在同一个集合中，即是否为同一个祖先。}//“靠左”原则，左边变成右边的BOSS。即把右边的集合，作为左边集合的子集合。//最后扫描有多少个独立的犯罪团伙int sum=0;for(int i=1;i<=n;i++)if(f[i]==i)sum++;printf("%d\n",sum);} return 0;
}