HDU 1272 小希的迷宮：並查集判斷圖是否為樹

題目大意

給定無向圖邊列表（以 0 0 分組，-1 -1 結束），判斷每組是否滿足：

1. 連通（無孤立點）。
2. 無環（任意兩點有且僅有一條簡單路徑）。
3. 空圖（無邊）視為合法。

輸出 Yes 或 No。

並查集判斷邏輯

• 初始化每點自成集合。
• 讀入邊 (u,v)：若 find(u)==find(v) 則成環 → 非法。
• 否則 union(u,v)。
• 組結束時：若曾檢測到環 → No；否則檢查連通性：所有出現過的點是否屬於同一集合（根節點數 = 1）。空圖（無點出現）直接 Yes。

關鍵細節

• 節點編號不連續、範圍未知（題目隱含 ≤ 100000），用陣列 fa[100005] 並記錄 min_id、max_id 遍歷檢查連通性。
• 出現過的點標記 vis[]。
• 輸入 0 0 表示組結束，需重置所有狀態處理下一組。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
const int MAXN = 100005;
int fa[MAXN];
bool vis[MAXN], ok;

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int a, int b) {
    a=find(a); b=find(b);
    if (a==b) ok=false; else fa[a]=b;
}
bool connected(int mn, int mx) {
    int root = -1;
    for (int i=mn;i<=mx;++i) if (vis[i]) {
        if (root==-1) root=find(i);
        else if (find(i)!=root) return false;
    }
    return true;
}

int main() {
    int u,v;
    while (scanf("%d%d",&u,&v)==2) {
        if (u==-1 && v==-1) break;
        if (u==0 && v==0) {
            static int mn=MAXN, mx=0;
            if (ok && (mx==0 || connected(mn,mx))) puts("Yes");
            else puts("No");
            // reset
            for (int i=0;imx) mx=u;
        if (vmx) mx=v;
        unite(u,v);
    }
    return 0;
}

複雜度

• 時間 O(E α(V))，空間 O(V)。

總結

小希的迷宮是並查集判斷「無向圖是否為樹」的經典應用。核心在於「合併時檢測環」與「最後驗證連通性」兩步，並正確處理空圖、非連續編號等邊界情況。