并查集算法多用于复杂关系的计算，比如亲戚的计算（计算总共有多少组亲戚关系，亲戚的亲戚也是亲戚），一个公司有多少组（老大的老大也是老大）。
算法要点：
1、用树（森林）存放关系，有关系的人一定有一个相同的根节点。
2、用数组存放节点关系，如tree【2】 = 3，表示2号人的根节点是3（2的老大是3）。
3、X和Y有关系的话，X的根节点更新为Y的根节点（与XY的顺序无关的）。注意是更新成Y的根节点而不是Y。
4、最后在数组中存在tree【Y】=Y的情况，那么这个点就是老大，也就是存在一棵树，也就是存在一组关系。
5、最后判断两个人是否有关系，还是需要去寻找两个人的根节点是不是相同，而不是两个人的上一个节点是不是相同，不是tree【X】 == tree【Y】,而是root（X）==root（Y）。
算法模型：
for（循环总人数）//初始化数组，一开始人与人之间都没有关系
{
tree【i】=i；
}
update（x，y）//X和Y有关系就更新两个节点的关系
{
rootx=root(x);
rooty=root(y);
if（rootx==rooty）两个点已经有关系不用更新
return;
else
tree【rooty】 = rootx；两个点没有关系，那么就让Y的根节点的值等于X的根节点的值，那么Y下面所有的有关系的人，当他们找到Y的时候就会下一步找到X的根节点了，就和X同一个根节点了，也就是有关系了。
}
root（x）//寻找根节点，有两种方法，一种是一直循环查到底，一种是递归同时更新所有相同关系的人为相同的节点，来减少下一次查询的时间
{
if（tree【x】==x）
return x；//已经是根节点了返回。
else
tree【x】 = root（tree【x】）//递归更新所有相同关系的人为相同的节点（最终节点）
return tree【x】；
}
#include<cstdio> #include<cstdlib> #include<iostream> using namespace std; /*并查集*/ int tree[100]; int getRoot2(int t) { int node = t; while (tree[node] != node)//不用递归每次都找一遍，时间复杂度较高 { node = tree[node]; } return node; } int getRoot(int t) { if (tree[t] == t) return t; tree[t] = getRoot2(tree[t]);//利用递归不断的更新自己的最终节点，使得有关系的几个人拥有尽可能多的相同的节点 return tree[t]; } void update(int x,int y) { int roota; int rootb; roota = getRoot(x);//获取根节点 rootb = getRoot(y); if(tree[roota] == tree[rootb])//这两个人已经有关系 return; tree[rootb] = roota;//这两个之前没有关系，现在要建立关系了 return; } int main() { int i;//循环变量 int n,m; int x,y;//暂存用户输入有关系的两个人 int sum=0;//用于保存最终输出的结果 cin>>n>>m;//总共最多有n人，m组关系 for (i = 1; i <= n; i++)//初始化，任意两人都没有关系 { tree[i] = i; } for (i = 1; i <= m; i++) { cin>>x>>y;//用户输入有关系的两个人 update(x,y);//更新关系 } for (i = 1; i <= n; i++)//用于输出一共有多少组毫不相干的关系（一共有几颗树） { if(tree[i] == i) sum++; } cout<<"一共有"<<sum<<"组关系"<<endl; for (i = 1; i <= n; i++) cout<<tree[i]<<" "; cout<<endl; while (cin>>x>>y)//输入两个数，看这两个人之间是否有关系 { if(getRoot(x) == getRoot(y)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } /* 10 9 1 2 3 4 5 2 4 6 2 6 8 7 9 7 1 6 2 4 Result:3 getRoot2:5 1 5 3 5 3 8 9 9 10 getRoot1:5 5 5 5 5 5 8 9 9 10 1 2 3 4 5 6 7 8 9 10 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 Result:4 */
总结一下，这个算法对于关系的处理上面真的很不错，很容易就能理清楚非常复杂的关系，而且递归更新使得算法本身速度快上不少，即使后面数据量大也不怕了。递归更新，在这里也叫路经压缩。