Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 提交好几遍了，每次都wa，题上，论坛里的数据都过了，就是wa，并查集做的，求大神。

Posted by 20020420 at 2018-09-29 11:38:58 on Problem 1308
```#include<cstdio>
int m,n,f[101],rank[101],num=0,swc=0;
int getf(int);
void merge(int,int);
int main()
{
while(scanf("%d%d",&n,&m)==2 && m!=-1 && n!=-1)
{
num++;
int x,y,sum=0,book[50001];

for(int i=1;i<=101;i++)//更新
{
f[i]=i;
book[i]=0;
}
swc=0;

if(n==m && n==0)//n,m输入
{
printf("Case %d is a tree.\n",num);
continue;
}
if(getf(n)==getf(m))
{
swc=1;
}
else
{
book[n]=1;
book[m]=1;
merge(n,m);
}

while(scanf("%d%d",&x,&y)==2 && x && y)//后续
{
if(getf(x)==getf(y))
{
swc=1;
}
else
{
book[x]=1;
book[y]=1;
merge(x,y);
}
}

for(int i=1;i<=101;i++)//几个树
{
if(book[i]==1 && i==getf(i))
{
sum++;
}
}

if(sum!=1)
{
swc=1;
}

if(swc==1)//输出
{
printf("Case %d is not a tree.\n",num);
}
else
{
printf("Case %d is a tree.\n",num);
}
}

getchar();
getchar();

return 0;
}

int getf(int x)
{
int r,j,k;
r=x;
while(r!=f[r])
{
r=f[r];
}
k=x;
while(k!=r)
{
j=f[k];
f[k]=r;
k=j;
}
return r;
}

void merge(int x,int y)
{
int i,j;
i=getf(x);
j=getf(y);
if(i!=j)
{
if(j!=y)
{
swc=1;
return ;
}
f[j]=i;
if(rank[i]<rank[j])
{
rank[i]=rank[j]+1;
}
if(rank[i]==rank[j])
{
rank[i]++;
}
}
return ;
}
```

Followed by: