這是一道非常棒的并查集入門題目，不懂的可以直接看下面的代碼：

#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];///剛剛開始數(shù)組開小了，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;

}

官網(wǎng)：

QQ是：