首页 > 代码库 > 【HDU1325】Is It A Tree?（并查集基础题）

【HDU1325】Is It A Tree?（并查集基础题）

2024-07-13 11:48:56   224人阅读

有以下坑点：

1.结束输入不一定-1，题目中的叙述只是说所有权值都为正值。

2.是否构成一棵树不能只判断是否只有一个根节点，没有环路，而且还需要判断每个节点的入度一定是1，不然就不是一棵树。

（无环路也可用树的性质：结点数 = 边树 + 1 来取代）

 

 1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cctype> 5 #include <cmath> 6 #include <string> 7 #include <cstdio> 8 #include <algorithm> 9 #include <numeric>10 using namespace std;11 12 const int maxn = 25;13 14 int  father[maxn];15 int  eage[maxn];16 bool vis[maxn], flag = 0;17 int sum = 0;18 19 int getFather (int x) {20     while (father[x] != x) {21         x = father[x];22     }23     return x;24 }25 26 void Union (int p, int q) {27     int x = getFather (p);28     int y = getFather (q);29     if (x != y) {30         father[y] = x;31         sum ++;32     } else {33         flag = 0;34     }35 }36 37 int main () {38     int x, y, cur = 0;39     while (cin >> x >> y) {40         if (x < 0 && y < 0) break;41         if (x == 0 && y == 0) {42             printf("Case %d is a tree.\n", ++ cur);43             continue;44         } else {45             flag = 1;46             memset(vis, 0, sizeof(vis));47             memset(eage, 0, sizeof(eage));48             for (int i = 0; i < maxn; ++ i) {49                 father[i] = i;50             }51             vis[x] = vis[y] = 1;52             Union(x, y);53             eage[y] ++;54             while (cin >> x >> y) {55                 if (x + y == 0) break;56                 vis[x] = vis[y] = 1;57                 Union(x, y);58                 eage[y] ++;59             }60             sort(eage, eage + maxn, greater<int>());61             int xx = 0;62             if (eage[0] > 1) flag = 0;63             for (int i = 1; i < maxn; ++ i) {64                 if (vis[i] && father[i] == i) {65                     xx ++;66                     if (xx > 1) {flag = 0; break;}67                 }68             }69             /*for (int i = 1 ; i < maxn; ++ i) {70                 cout << vis[i] <<  " " ;71             }*/72 73             if (flag) printf("Case %d is a tree.\n", ++ cur);74             else printf("Case %d is not a tree.\n", ++ cur);75         }76     }77     return 0;78 }


联系
我们