好朋友（并查集与路径压缩的结合体）

本文主要是介绍好朋友（并查集与路径压缩的结合体），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

1. A和B是好朋友，则B与A也是好朋友；

2.如果A和C是好朋友，B和C也是好朋友，那么 A和B也是好朋友。

问：现在给出所有好朋友的对数，可以把这些朋友分成多少组，满足每组中的任意两只数码宝贝都是好朋友，且任意两组之间的数码宝贝都不是好朋友。

输入：

输入第一行有两个正整数n（小于、等于100），m（小于等于100），分别表示数码宝贝的编号1～n。

接下来有m行每行a，b，表示a与b是好朋友。

输出：

输出组数。

代码：

#include<cstdio>
const int N=110;
int father[N];
bool isroot[N];//存放每个结点是否作为某个集合的根节点
int findfather(int x)//查找x所在的集合的根节点
{
int a=x;
while(x!=father[x])
x=father[x];
while(a!=father[a])
{
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void Union(int a,int b)
{
int faA=findfather(a);
int faB=findfather(b);
if(faA!=faB)
father[faA]=faB;
}
void init(int n)
{
for(int i=1;i<=n;i++)
{
father[i]=i;
isroot[i]=false;
}

}
int main()
{
int n,m,a,b;
scanf("%d%d",&n,&m);
init(n);//进行初始化，让每个数的根节点等于自身
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
Union(a,b);//合并两个集合，并找出其根节点，如果不相同，则分别独立
}
for(int i=1;i<=n;i++)
{
isroot[findfather(i)]=true;//根节点为真时，则表示有一个根节点
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=isroot[i];
}
printf("%d\n",ans);
return 0;
}