在我看来，简单的并查集算法的问题主要分为几步。
- 初始化
- 开始合并
- 寻找最后有多少个根节点
用一个例题来说明比较容易理解。
例：
描述
有n个人，编号1-n。
现在有一个舞会，在舞会上，大家会相互介绍自己的朋友。
即： 如果a认识b，b认识c。那么在舞会上，a就会通过b认识到c。
现在，给出m个关系
每个关系描述：a b
表示 编号为a和编号为b的人是朋友关系。
格式
输入格式
输入n和m
接下来m行，每行为a b
输出格式
最后问，会有多少个朋友圈。
样例
样例输入
5 3
1 2
2 3
4 5
样例输出
2
思路
思路很简单，你可以假设每个朋友圈中都有一个头领，假设a和b最终头领都是同一个人，那么他们就属于同一个朋友圈。而如果两个朋友圈中的人结交为朋友又咋办呢，这时候只需要小头领c认小头领d为头领就好了，这样朋友圈c和朋友圈d就有同一个头领d了。最后，我们只需要找有多少个头领就好了。
初始化
我们假设刚刚开始有n个人，这n个人每个人都是一个朋友圈，各搞各的，谁也不理谁，那他们的头领就是他们自己。
int nnn[n]//这里是因为我不知道具体数据有多大，所以用这种不规范的写法
for(i=1;i<=n;i++)
nnn[i]=i;好勒，这样便已经是初始化完毕。
合并
等下，在合并朋友圈之前，我们先要确认一下我们是不是一个朋友圈的人。
如果是一个朋友圈，就不需要合并了，如果不是一个朋友圈的，我们就得换另外一个老大，做大朋友圈的老大。
寻找老大是谁
这里有一种递归版本和一种普通版
递归版本
int find(int a,int nnn[])
{
if(nnn[a]==a)
return a;
else
{
nnn[a]=find(nnn[a],nnn);//这里是路径压缩，待会有解释
return nnn[a];
}
}非递归版
int findroot(int root,int a[])
{
int son,temp;
son=root;
while(root!=a[root])
{
root=a[root];
}
while(son!=root)//这里是路径压缩，待会有解释
{
temp=a[son];
a[son]=root;
son=temp;
}
return root;
}在我们实际编写代码时候，我发现如果一个人他的小头领不是老大的话，可能会向上查询很多次，于是我们可以直接将他的小头领，变更为老大，这样我们便减少了一定的时间。
现在是合并
我们要看看到底两个人是不是同一个老大
void hebin(int a,int b,int nnn[])//原谅我英语不好，不会合并的英文
{
int root1,root2;
root1=find(a,nnn);
root2=find(b,nnn);
if(root1!=root2)
{
nnn[root2]=root1;//老大root2的头领从他自己变更为root1
}
return;
}最后
我们遍历寻找还有多少个自己是自己头领既有多少个朋友圈老大就好了
完整代码
#include <stdio.h>
int find(int a,int nnn[])
{
if(nnn[a]==a)
return a;
else
{
nnn[a]=find(nnn[a],nnn);
return nnn[a];
}
}
void hebin(int a,int b,int nnn[])
{
int root1,root2;
root1=find(a,nnn);
root2=find(b,nnn);
if(root1!=root2)
{
nnn[root2]=root1;
}
return;
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
int i,nnn[n];
for(i=1;i<=n;i++)
nnn[i]=i;
while(m--)
{
int a,b;
scanf("%d %d",&a,&b);
hebin(a,b,nnn);
}
int jishu=0;
for(i=1;i<=n;i++)
if(nnn[i]==i)
jishu++;
printf("%d\n",jishu);
}
}