HDU 1272 小希的迷宮：並查集判斷樹結構

題目重述

給定若干條雙向邊（房間連接），判斷圖是否為一棵**樹**：連通且無環。輸入以 0 0 結束一組測試，-1 -1 結束文件。房間編號 ≤ 100,000。

樹的等價條件

無向圖為樹 ⇔ 無環 且 邊數 = 節點數 - 1 且 連通。
並查集可同時檢測環與連通性：

• 合併時若兩端點已在同一集合 → 存在環。
• 統計實際出現的節點數 V 與邊數 E，最後驗證 E == V-1 且無環標記。

多樹（森林）陷阱

輸入可能包含多個不相連分量。若中途發現環直接 break 會漏讀後續邊，導致下一組測試讀錯。**必須讀完當前測試所有邊**，僅設置標記，最後統一判斷。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 100005;

int fa[MAXV];
bool vis[MAXV];

int findRoot(int x) {
    return fa[x] == x ? x : fa[x] = findRoot(fa[x]);
}
void unite(int x, int y) {
    x = findRoot(x); y = findRoot(y);
    if (x != y) fa[x] = y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    while (cin >> a >> b) {
        if (a == -1 && b == -1) break;

        fill(vis, vis + MAXV, false);
        iota(fa, fa + MAXV, 0);

        int edges = 0, vertices = 0;
        bool hasCycle = false;

        auto process = [&](int u, int v) {
            if (!vis[u]) { vis[u] = true; ++vertices; }
            if (!vis[v]) { vis[v] = true; ++vertices; }
            ++edges;
            if (findRoot(u) == findRoot(v)) hasCycle = true;
            else unite(u, v);
        };

        process(a, b);
        while (cin >> a >> b) {
            if (a == 0 && b == 0) break;
            process(a, b);
        }

        if (!hasCycle && edges == vertices - 1) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

複雜度與技巧

• 時間近似 O(E α(V))，極快。
• 路徑壓縮 + 按秩合併（此處簡化）保證效率。
• 輸入以空行分隔測試案例，cin 自動跳過空白，無需額外處理。