Description
Input
Output
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.
跟小希的迷宫差不多，需要注意的是小希的迷宫是无向图，而本题是有向图。
判断是不是一棵树需要的条件如下：
1. 肯定满足只有一个树根,只有一个入度为0的点。
2. 除了根每个点的入度只能为1
3. 无环
4. n个点只能有n-1个边
直接从小希的迷宫进行改的，不过本代码在poj AC ,但是HDU Wrong Answer
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 int set[10005]; 7 bool vis[10005]; 8 bool flag; 9 int find(int x) 10 { 11 return set[x]==x?x:set[x]=find(set[x]); 12 } 13 int main() 14 { 15 int a,b,k=0; 16 while(scanf("%d%d",&a,&b)) 17 { 18 int maxn=-1; 19 if(a<0&&b<0) 20 break; 21 flag=true; 22 if(a==0&&b==0) 23 { 24 printf("Case %d is a tree.\n",++k); 25 continue; 26 } 27 for(int i=1; i<10005; i++) 28 { 29 set[i]=i; 30 vis[i]=false; 31 } 32 while(a||b) 33 { 34 maxn=max(maxn,max(a,b)); 35 vis[a]=true,vis[b]=true; 36 int x=find(a); 37 int y=find(b); 38 if(x!=y) 39 { 40 // if(x<y) 41 set[x]=y; 42 //else 43 //set[y]=x; 44 } 45 else 46 flag=false; 47 scanf("%d%d",&a,&b); 48 } 49 int ans=0; 50 for(int i=1; i<=maxn; i++) 51 { 52 if(vis[i] && set[i]==i) 53 ans++; 54 if(ans>1) 55 flag=false; 56 } 57 if(flag) 58 printf("Case %d is a tree.\n",++k); 59 else 60 printf("Case %d is not a tree.\n",++k); 61 } 62 return 0; 63 }
hdu 1325 && poj 1308 Is It A Tree?(并查集)
原文：http://www.cnblogs.com/cxbky/p/4892961.html
