跟小希的迷宫有些相似。但却不知道为什么那些做法放这里就超时了。……
View Code
1 2 #include <iostream> 3 #include <string.h> 4 #include <string> 5 #include <cstdio> 6 using namespace std; 7 int leftt[10005],rightt[10005],father[10005]; 8 int find(int x){ 9 if(father[x]==-1) 10 return x; 11 return find(father[x]); 12 } 13 void unionset(int x,int y){ 14 father[y]=x; 15 } 16 int main(){ 17 18 int a,b; 19 int count=1; 20 while(1){ 21 memset(father,-1,sizeof(father)); 22 memset(leftt,0,sizeof(leftt)); 23 memset(rightt,0,sizeof(rightt)); 24 scanf("%d%d",&a,&b); 25 if(a<0&&b<0) 26 return 0; 27 else if(a==0&&b==0) 28 printf("Case %d is a tree.\n",count++); 29 else{ 30 int i=1; 31 leftt[i]=a;rightt[i]=b; 32 while(scanf("%d%d",&a,&b)&&a&&b){ 33 i++; 34 leftt[i]=a; 35 rightt[i]=b; 36 } 37 int flag=1; 38 for(int j=1;j<=i;++j){ 39 int x=find(leftt[j]); 40 int y=find(rightt[j]); 41 if(x==y||y!=rightt[j]){ 42 flag=0; 43 break; 44 } 45 unionset(x,y); 46 } 47 if(flag){ 48 int xx=find(leftt[1]); 49 50 int tt; 51 for(tt=2;tt<=i;++tt){ 52 if(xx!=find(leftt[tt])) 53 break; 54 55 } 56 if(tt>i) 57 printf("Case %d is a tree.\n",count++); 58 else 59 printf("Case %d is not a tree.\n",count++); 60 } 61 else 62 printf("Case %d is not a tree.\n",count++); 63 } 64 } 65 return 0; 66 }