HDU 2120 Ice_cream's world I：基礎並查集計算環數

題目大意

給定 N（≤1000）個瞭望塔與 M（≤10000）條圍牆（無向邊），圍牆將土地分割成若干塊。每塊被圍牆包圍的土地只能分給一個 ACMer。求最多能分給多少 ACMer（即圖中獨立環的數量）。

解題思路

無向圖中，每加一條邊若連接的兩點已在同一連通分量，則形成一個新環。使用並查集：
初始每點自成一集。遍歷邊 (u, v)：
- 若 find(u) == find(v)，環計數 +1。
- 否則 union(u, v)。
最終環計數即為答案。

代碼實現

#include <cstdio>
const int N = 1015;
int fa[N], n;

void init() { for (int i = 0; i <= n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return true; // 形成環
    fa[x] = y; return false;
}

int main() {
    int m, ans, x, y;
    while (scanf("%d%d", &n, &m) == 2) {
        init(); ans = 0;
        while (m--) { scanf("%d%d", &x, &y); if (unite(x, y)) ++ans; }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 時間：O(M α(N))，近似線性。
• 空間：O(N)。

注意

• 題目說明「任意兩個房間都是相互連通的」對應強連通，但此題為無向圖，環即代表一塊被圍牆包圍的土地。
• 並查集路徑壓縮確保效率。
• 輸入至 EOF，多測資循環處理。