#include<stdio.h>
#include<string.h>//判斷是否有環(huán)，判斷是否是一個(gè)根節(jié)點(diǎn)。判斷空樹(shù)的情況
#define N 1000000
int pre[N+10],dis[N+10],degree[N+10];
int find(int n) {
return pre[n]=n==pre[n]?n:find(pre[n]);
}
int main() {
int a,b,cnt,flag,f1,f2,i,min,max,k=0,w,u;
while(scanf("%d%d",&a,&b),a!=-1||b!=-1) {
if(a==0&&b==0) {//和杭電不一樣他是一個(gè)樹(shù)剛開(kāi)始錯(cuò)在這
printf("Case %d is a tree.\n",++k);
continue;
}
for(i=1;i<=N;i++)
pre[i]=i;
f1=find(a);
f2=find(b);
degree[a]++;
pre[f2]=f1;
dis[a]=dis[b]=1;
min=a>b?b:a;
max=a>b?a:b;
w=0;
if(min==max)//與節(jié)點(diǎn)自身相連不是一棵樹(shù)
w=1;
flag=0;
while(scanf("%d%d",&a,&b),a||b) {
degree[a]++;
if(a==b)
w=1;
f1=find(a);
f2=find(b);
if(f1==f2)
flag=1;
else
pre[f2]=f1;
dis[a]=dis[b]=1;
min=min<a?min:a;
min=min<b?min:b;
max=max>a?max:a;
max=max>b?max:b;
}
if(flag||w) {
printf("Case %d is not a tree.\n",++k);
continue;
}
cnt=0;u=0;
/*for(i=min;i<=max;i++)
if(degree[i]>cnt)
cnt=degree[i];
for(i=min;i<=max;i++)
if(cnt==degree[i])
u++;
if(u>1) {
printf("Case %d is not a tree.\n",++k);
continue;
}*/

cnt=0;
for(i=min;i<=max;i++)
if(pre[i]==i&&dis[i])
cnt++;
if(cnt==1)
printf("Case %d is a tree.\n",++k);
else
printf("Case %d is not a tree.\n",++k);
}
return 0;
}//測(cè)試數(shù)據(jù)1: 0 0 空樹(shù)是一棵樹(shù)
//2: 1 1 0 0 不是樹(shù) 不能自己指向自己
//3: 1 2 1 2 0 0 不是樹(shù)....自己開(kāi)始一直在這么WA ?好郁悶 重復(fù)都不行呀~~5555
//4: 1 2 2 3 4 5 不是樹(shù) ?森林不算是樹(shù)(主要是注意自己)
//5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 ?注意 一個(gè)節(jié)點(diǎn)在指向自己的父親或祖先 都是錯(cuò)誤的 即 9-->1 錯(cuò)
//6: 1 2 2 1 0 0 也是錯(cuò)誤的

轉(zhuǎn)載于:https://www.cnblogs.com/thefirstfeeling/p/4410965.html

總結(jié)

以上是生活随笔為你收集整理的poj1308的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。