HDU 2120 Ice_cream's World I 並查集計數環

問題描述

給定 N 個瞭望塔（節點）和 M 條圍牆（邊），圍牆將土地分割成若干塊。每塊被圍牆包圍的土地只能分給一個 ACMer。求最多能分給多少個 ACMer，即平面圖中的面數（含外部無限面）。

歐拉公式與面數計算

對於連通平面圖：V - E + F = 2（含外部面）。
若圖有 k 個連通分量：V - E + F = 1 + k。
本題中，每條邊添加時若連接同一連通分量的兩個節點，會形成一個新環，面數 +1。因此答案 = 1 + 成環數量。

並查集檢測成環

遍歷所有邊 (u, v)：
若 u 和 v 已在同一集合 → 形成環，計數器 ++
否則 → 合併兩個集合

代碼實現

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

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; ++i) parent[i] = i;
        int cycles = 0;
        for (int i = 0; i < m; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            int fa = find(a), fb = find(b);
            if (fa == fb) ++cycles;
            else parent[fa] = fb;
        }
        printf("%d\n", cycles + 1); // 包含外部面
    }
    return 0;
}

關鍵點

• 節點編號 0 到 N-1
• 多組測試數據，EOF 結束
• 並查集無需路徑壓縮也可 AC，但建議加上
• 答案 = 成環數 + 1（外部無限面）