这是一道非常棒的并查集入门题目，不懂的可以直接看下面的代码：
#include
#include
usingnamespacestd;
intf[50010];
intsum=0;
//Accepted360K313MS
intfind1（intx）{
if（f[x]!=x）{
f[x]=find1（f[x]）；
}
returnf[x];
}
voidmerge1（inta,intb）{
intf1=find1（a）；
intf2=find1（b）；
if（f1!=f2）{
f[f2]=f1;
sum--;
}
}
intmain（）
{
intn,m,p=1;
while（scanf（"%d%d",&n,&m）!=EOF）{
if（n==0&&m==0）{break;}
for（inti=1;i<=n;i++）{
f[i]=i;
}
sum=n;
for（inti=1;i<=m;i++）{
inta,b;
scanf（"%d%d",&a,&b）；
merge1（a,b）；
}
printf（"Case%d:%d\n",p++,sum）；
}
return0;
}
//另一版本，大概思路相似，仅仅就并的时候，少的像多的并。
#include
#include
#include
usingnamespacestd;
//Accepted556K297MS
structstudent{
intindex;
intnum;
student（）{
num=1;
}
};
studentf[50010];///刚刚开始数组开小了，runtimeerror!
intn,m,sum=0;
intfind1（intx）{//查找
if（f[x].index!=x）{
f[x].index=find1（f[x].index）；
}
returnf[x].index;
}
voidmerge1（inta,intb）{//合并
intf1=find1（f[a].index）；
intf2=find1（f[b].index）；
if（f1!=f2）{
if（f[f1].num>=f[f2].num）{
f[f1].num+=f[f2].num;
f[f2].index=f1;
}
else{
f[f2].num+=f[f1].num;
f[f1].index=f2;
}
sum--;
}
}
voidinit（）{//初始化
sum=n;
for（inti=1;i<=n;i++）{
f[i].index=i;
}
}
intmain（）
{
intp=1;
while（scanf（"%d%d",&n,&m）!=EOF）{
if（！n&&!m）{break;}
init（）；
for（inti=1;i<=m;i++）{
inta,b;
scanf（"%d%d",&a,&b）；
merge1（a,b）；
}
printf（"Case%d:%d\n",p++,sum）；
}
return0;
}
官网：
QQ是：
