POJ 1308 Is It A Tree? 并查集判斷樹結構

題目

給定有向邊列表，判斷是否構成一棵樹。樹的定義：有唯一根節點（入度 0），其他節點入度 1，從根到任意節點有唯一路徑（無環、連通）。輸入以 0 0 結束一個測試用例，-1 -1 結束所有。

并查集解法

遍歷邊 (u,v)：
1. 若 u 和 v 已在同一集合 → 有環，非樹。
2. 記錄入度，若 v 入度 > 1 → 非樹。
3. 合併 u, v。
最後檢查：邊數 = 節點數 - 1 且無環且恰有一個入度為 0 的節點（或空圖視為樹）。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int fa[MAXN], inDeg[MAXN];
bool vis[MAXN];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    int u, v, caseNo = 1;
    while (cin >> u >> v) {
        if (u == -1 && v == -1) break;
        if (u == 0 && v == 0) {
            // 判斷邏輯
            bool isTree = true;
            int nodes = 0, edges = 0, rootCount = 0;
            for (int i = 1; i < MAXN; i++) if (vis[i]) {
                nodes++;
                if (inDeg[i] == 0) rootCount++;
                else if (inDeg[i] > 1) isTree = false;
                edges++;
            }
            if (nodes == 0) isTree = true; // 空樹
            else if (rootCount != 1 || edges != nodes - 1) isTree = false;
            cout << "Case " << caseNo++ << " is " << (isTree ? "a tree." : "not a tree.") << endl;
            // 重置
            fill(fa, fa + MAXN, 0);
            fill(inDeg, inDeg + MAXN, 0);
            fill(vis, vis + MAXN, false);
            for (int i = 0; i < MAXN; i++) fa[i] = i;
            continue;
        }
        vis[u] = vis[v] = true;
        if (find(u) == find(v)) { /* 標記有環 */ }
        else fa[find(v)] = find(u);
        inDeg[v]++;
    }
    return 0;
}