POJ 2524 Ubiquitous Religions - 並查集求宗教上界

題目大意

大學有 n (≤ 50,000) 位學生，已知 m 對「同教」關係。每生至多屬一教派。求「可能存在的不同教派數上界」。

輸入多組測資，以 0 0 結束。輸出格式：Case X: Y。

核心觀察

• 「同教」是等價關係 → 並查集維護連通分量。
• 每個連通分量最多只能屬於同一教派 → 分量數即為教派數上界。
• 初始各自為教派，每合併一對不同分量，教派數 -1。

算法流程

1. makeset(n)：初始化 parent[i]=i, rank[i]=0。
2. 讀入 m 條邊，unionset(u,v)：按秩合併 + 路徑壓縮。
3. 掃描 1..n，統計 parent[i]==i 的根節點數 → 答案。

完整 C++ 代碼 (G++ 通過)

#include 
using namespace std;

const int MAXN = 50000 + 5;
int parent_[MAXN], rnk[MAXN];

void makeset(int n) {
    iota(parent_ + 1, parent_ + n + 1, 1);
    fill(rnk + 1, rnk + n + 1, 0);
}

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

void unionset(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    parent_[y] = x;
    if (rnk[x] == rnk[y]) ++rnk[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, tc = 1;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        makeset(n);
        for (int i = 0, u, v; i < m; ++i) {
            cin >> u >> v;
            unionset(u, v);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) if (find(i) == i) ++ans;
        cout << "Case " << tc++ << ": " << ans << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O((n+m) α(n))，α 為反阿克曼函數，實際近似常數。
• 空間：O(n)。

關鍵優化提醒

• 輸入量大，務必用 ios::sync_with_stdio(false); cin.tie(nullptr); 或 scanf。
• 路徑壓縮 + 按秩合併是標準並查集寫法，避免退化成鏈表。

本題是並查集入門經典，掌握「動態連通性 → 分量計數」模式，後續遇到「分組、圈數、島嶼數」等問題皆可秒殺。