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.
//题目大意：判断是否为树，输入0 0结束循环，-1 -1结束程序，6 8代表6为8的根结点。树的定义可以百度。
注意的地方如下：
1: 0 0 空树是一棵树
2: 1 1 0 0 不是树 不能自己指向自己
2: 1 2 1 2 0 0 不是树 重复都不行= =
2: 1 2 2 1 0 0 也是错误
3: 1 2 2 3 4 5 不是树，森林不是树
代码如下：
#include <iostream> #include <cstdio> using namespace std; const int maxn=105; int a,b,fir,dad[maxn]; int f[maxn]; void fuqin() {for (int x=1;x<=105;x++) {dad[x]=x; f[x]=0;} } int find(int x) { int p = x, t; while (dad[p] != p) p = dad[p]; while (x != p) { t = dad[x]; dad[x] = p; x = t; } return x; } void union1(int x, int y){ x = find(x); y = find(y); if(x == y) return; dad[y] = x; } int main() { int t=1; while (scanf("%d %d",&a,&b)!=EOF) { if(a==-1&&b==-1)break; if(a==0&&b==0) {printf("Case %d is a tree.\n", t ++);continue;}// 第1类判断： 空树是一棵树。 fuqin(); f[a]=f[b]=1; fir = a; bool tree = 1; if(a == b) tree = 0; else union1(a, b); while(scanf("%d %d", &a, &b) && a != 0){ f[a] = f[b] = 1; if(find(a) == find(b)) tree = 0;// 第2类判断。 union1(a,b); } for(a = 1; a < 100; a ++)// 第3类判断：不能为森林。 if(f[a] && find(a) != find(fir)) tree = 0; if(tree) printf("Case %d is a tree.\n", t ++); else printf("Case %d is not a tree.\n", t ++); } return 0; }
原文：http://www.cnblogs.com/gdvxfgv/p/5697154.html
