并查集模板
#include<stdio.h>
#define maxn 100005 //定义maxn
using namespace std;
int s[maxn];
int find(int x)
{
if(s[x]==x)
{
return x;
}
else
{
return find(s[x]); //找上一个，一直到一样，即源头
}
}
void Union(int x,int y)
{
int x1,y1;
x1=find(x);
y1=find(y);
if(x1!=y1)
{
s[y1]=x1;
}
}
int main()
{
int i,j,count,a,b;
for(i=0;i<=maxn;i++) //用了maxn;
{
s[i]=i; //赋值
}
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a==0&&b==0) //跳出循环
{
break;
}
if(find(a)==find(b)) //判断a,b是否联通
{
printf("YES *\n");
}
else
{
printf("NO\n");
Union(a,b); //联通a,b 把b给a（以a为源头）
// printf("a=%d b=%d\n",find(a),find(b));
if(find(a)==find(b))
{
printf("YES #\n");
}
else
{
printf("NO !!!!!\n"); //都联通了，好像已经没用了。。。。。。
}
}
}
count=0;
for(j=0;j<maxn;j++) //用了maxn;
{
if(s[j]==j)
{
count++;
}
}
printf("count=%d\n",count); //输出还有多少团体，联通的算一个了
return 0;
}
