本文共 2174 字，大约阅读时间需要 7 分钟。
判断给定的结点是否构成一棵树。
注意：结点集合为空构成空树；有重复的边不是树；节点有指向自己的边不是树；树只有一个根节点；
思想：使用并查集。将添加的结点合并，最终只有一个结点。注意新加的结点b为a的长辈。
#include //#include using namespace std;/* tree: 1. no cycle 2. noly indegree==0 3. else indegree==1*/const int size = 100000;//map hash;int fa[size];bool vis[size];int Find(int x){ if (x == fa[x]) return x; return fa[x] = Find(fa[x]);}int main(){ int a, b; int cas = 1; int yes = 1; int i, maxn; while (scanf("%d %d",&a,&b)!=EOF) { if (a < 0 || b < 0) break; if (0 == a && 0 == b)// 空树 { printf("Case %d is a tree.\n",cas++); continue; } yes = 1; maxn = 0; for (i = 0; i < size; ++i) { fa[i] = i; vis[i] = 0; } if (a != b) fa[b] = a; else yes = 0; // self-directed vis[b] = vis[a] = 1; maxn = a > b? a :b; while (scanf("%d %d",&a,&b)!=EOF) { if (0 == a || 0 == b) break; if (!yes || a== b) { yes = 0; // self-directed continue; } vis[a] = vis[b] = 1; maxn = maxn>a?maxn:a; maxn = maxn>b?maxn:b; if (fa[b] != b || Find(a) == Find(b)) //b has more fa, b is a's father { yes = 0; //break; } else fa[b] = Find(a); } a = 0; for (i = 1; i <= maxn; ++i) { if (vis[i]) { if (Find(i) == i) a++; if (a > 1) { yes = 0; break; } } } if (a != 1) yes = 0; printf("Case %d is ",cas++); if (yes) printf("a tree.\n"); else printf("not a tree.\n"); } //system("pause"); return 0;}
转载于:https://my.oschina.net/acemumu/blog/101922
