HDU 1272 小希的迷宮：並查集判斷樹的合法性

題目大意

給定若干條邊 (x, y)，構成無向圖。每組數據以 0 0 結束，全部數據以 -1 -1 結束。判斷每組邊是否構成一棵樹（即連通且無環）。輸出 "Yes" 或 "No"。

並查集解法

並查集維護連通分量。處理每條邊 (x, y)：

• 若 x 和 y 已在同一集合（find(x) == find(y)），則成環 → 標記非樹。
• 否則合併兩集合。

最後檢查：若無環且只有一個連通分量（即所有出現過的節點屬於同一根），則是樹。

代碼實現

#include <cstdio>
const int MAXN = 100005;
int parent[MAXN];
bool visited[MAXN];

int findRoot(int x) {
    while (x != parent[x]) x = parent[x];
    return x;
}

void init() {
    for (int i = 1; i < MAXN; i++) {
        parent[i] = i;
        visited[i] = false;
    }
}

int main() {
    int x, y;
    bool isTree = true;
    int components = 0;
    init();
    while (scanf("%d%d", &x, &y) == 2) {
        if (x == -1 && y == -1) break;
        if (x == 0 && y == 0) {
            // 判斷當前圖
            if (!isTree) puts("No");
            else {
                int roots = 0;
                for (int i = 1; i < MAXN; i++)
                    if (visited[i] && parent[i] == i) roots++;
                puts(roots == 1 ? "Yes" : "No");
            }
            // 重置
            isTree = true;
            init();
        } else {
            visited[x] = visited[y] = true;
            int rx = findRoot(x), ry = findRoot(y);
            if (rx == ry) isTree = false;
            else parent[ry] = rx;
        }
    }
    return 0;
}

關鍵點

• 節點編號範圍未給出，假設 ≤ 100000，開大數組。
• 每組數據需重置並查集與 visited 數組。
• 並查集未做路徑壓縮，但數據量小足夠；可加壓縮優化。

總結

並查集是判斷無向圖是否為樹的經典工具：檢測環（合併前同根）+ 檢測連通性（最終根數量為 1）。本題輸入格式特殊，注意 0 0 分隔測試案例，-1 -1 結束整個輸入。