hdu 1325数据弱

#include<stdio.h>//判断是否有环，判断是否有点，判断是否是一个父节点

#include<string.h>

#define N 1000000

int pre[N+10],dis[N+10];

int find(int n ) {

if(pre[n]!=n)

return pre[n]=find(pre[n]);

return pre[n];

}

int main() {

int n,m,i,a,b,j,cnt,flag,f1,f2,k=0,min,max;

while(scanf("%d%d",&a,&b),a>=00&&b>=0){//判断条件需注意

if(a==0&&b==0) {

printf("Case %d is not a tree.\n",++k);//和1272不一样如果没有节点就不是树

continue;

}

for(i=1;i<=N;i++)

pre[i]=i;

f1=find(a);

f2=find(b);

pre[f2]=f1;

dis[a]=dis[b]=1;

min=a>b?b:a;

max=a>b?a:b;

flag=0;

while(scanf("%d%d",&a,&b),a&&b) {

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) {

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;

}

巴特西

hdu 1325数据弱

最新文章

热门文章