并查集判斷樹結構：POJ 1308 / HDU 1272 完整解法

樹的充要條件

1. **無環**：任意兩節點最多有一條路徑。
2. **連通**：只有一個連通分量（根節點唯一）。
3. **邊數 = 節點數 − 1**（隱含前兩條）。

并查集可同時檢測環與連通性。

算法流程

1. 初始化每個節點父節點指向自己。
2. 讀入邊 (u,v)：
   `find(u) == find(v)` → 成環 → 非樹。
   否則 `union(u,v)`。
3. 輸入結束 (0 0) 後，統計根節點個數。若 >1 → 森林 → 非樹。
   特殊情況：空輸入 (0 0) 直接是樹。

代碼（POJ 1308）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;

int fa[MAXN];
bool hasEdge[MAXN];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int u, v, caseNo = 1;
    while (cin >> u >> v) {
        if (u == -1 && v == -1) break;
        fill(fa, fa + MAXN, 0);
        fill(hasEdge, hasEdge + MAXN, false);
        bool isTree = true;
        int nodes = 0;
        auto init = [&](int x) {
            if (!hasEdge[x]) { hasEdge[x] = true; fa[x] = x; nodes++; }
        };
        while (u != 0 || v != 0) {
            init(u); init(v);
            int fu = find(u), fv = find(v);
            if (fu == fv) isTree = false; // 成環
            else fa[fu] = fv;
            cin >> u >> v;
        }
        // 統計根
        int roots = 0;
        for (int i = 1; i < MAXN; ++i)
            if (hasEdge[i] && find(i) == i) roots++;
        if (roots != 1) isTree = false; // 空圖 roots=0 視為樹
        if (nodes == 0) isTree = true;  // 空樹
        cout << "Case " << caseNo++ << " is " << (isTree ? "" : "not ") << "a tree.\n";
    }
    return 0;
}

HDU 1272 差異

HDU 1272 只需輸出 `Yes`/`No`，且節點編號上限 10⁵，邏輯完全相同，調整數組大小與輸出格式即可。