并查集的应用注意是“有且仅有”就要保证最终只有一个集合,且每个点都只有一条路。
#include<stdio.h>
int father[100005],depth[100005];
int a[200005];
void init()
{
int i;
for(i = 1; i < 100005;i ++)
{
father[i] = i;
depth[i] = 0;
}
}
int find(int x)
{
if(x==father[x])
return x;
else
return father[x] = find(father[x]);
}
void unit(int x,int y)
{
x = find(x);
y = find(y);
if(x==y)
return ;
if(depth[x]<depth[y])
{
father[x] = y;
}
else
{
if(depth[x]>depth[y])
father[y] = x;
else
{
father[x] = y;
depth[y]++;
}
}
}
int main()
{
int i,j,k = 1,flag,con,temp = -1;
while(~scanf("%d%d",&a[k],&a[k+1])&&(a[k]!=-1||a[k+1]!=-1))
{
con = 0;
if(a[k]==0&&a[k+1]==0)
{
printf("Yes
");
continue ;
}
flag = 0;
init();
unit(a[k],a[k+1]);
k += 2;
while(~scanf("%d%d",&a[k],&a[k+1])&&(a[k]||a[k+1]))
{
if(find(a[k])==find(a[k+1])) //判断是否只有一条路,做到“有”。
flag = 1;
else
unit(a[k],a[k+1]);
k += 2;
}
for(j = 1;j < k;j ++)
{
if(a[j]==find(a[j])&&(temp!=a[j])) //判断是否只有一个集合,做到”仅有“。
{
con++;
temp = a[j];
}
if(con==2)
break ;
}
if(k==3&&(a[1]==a[2]))
flag = 1;
if(!flag&&(con==1))
printf("Yes
");
else
printf("No
");
k = 1;
temp = -1;
}
return 0;
}