简介：
并查集是树的一种数据结构，用于处理多组不相交际集合之间的间接关系。集是单元素构成的集合，查是查找两两集合是否有关系，并就是把有联系的集合合并。如擒贼先擒王，把最终的boss找出来。
例题详细介绍：
题目：
今天是伊格纳修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格纳修斯想知道他至少需要多少张桌子。你必须注意到并非所有的朋友都相互认识，所有的朋友都不想和陌生人呆在一起。
这个问题的一个重要规则是，如果我告诉你A知道B，B知道C，那意味着A，B，C彼此了解，所以他们可以留在一个表中。
例如：如果我告诉你A知道B，B知道C，D知道E，所以A，B，C可以留在一个表中，D，E必须留在另一个表中。所以Ignatius至少需要2张桌子。
输入
输入以整数T（1 <= T <= 25）开始，表示测试用例的数量。然后是T测试案例。每个测试用例以两个整数N和M开始（1 <= N，M <= 1000）。 N表示朋友的数量，朋友从1到N标记。然后M行跟随。每一行由两个整数A和B（A！= B）组成，这意味着朋友A和朋友B彼此了解。两个案例之间会有一个空白行。
产量
对于每个测试用例，只输出Ignatius至少需要多少个表。不要打印任何空白。
Sample Input
2 5 3 1 2 2 3 4 5 5 1 2 5
Sample Output
2 4
题意：就是如果有联系的人可以坐一张桌子上，如果没有联系就单独一个人坐，一共需要多少张桌子。具体算法代码介绍：
#include<stdio.h> int f[51001]={0},n,m; void init()//初始化表示刚开始自己一个人坐一张桌子，互不影响 { int i; for(i=1;i<=n;i++) f[i]=i; return; } int getf(int v)//这个是找有关系的人，不停去找，直到找到最初始有关系的人，既擒贼先擒王 { if(f[v]==v) return v; else { f[v]=getf(f[v]);//递归去寻找，压缩路径 return f[v]; } } void merge(int v,int u) { int t1,t2; t1=getf(v); t2=getf(u);//t1,t2分别表示v,u的最终有关系的人 if(t1!=t2) f[t2]=t1;//判断两人是否有关系，既并于一个集合 return; } int main() { int i,x,y,sum; int cas=1; int N; scanf("%d",&N); while(N--) { sum=0; scanf("%d%d",&n,&m); init(); for(i=1;i<=m;i++) {//合并有关系的人 scanf("%d%d",&x,&y); merge(x,y); } for(i=1;i<=n;i++)//最后扫描一共需要多少桌 { if(f[i]==i) sum++; } printf("%d\n",sum); } return 0; }
