POJ 2524：Ubiquitous Religions - 並查集統計集合數

問題描述

n ≤ 50000 名學生，m 對「信仰相同」關係。每人至多屬於一個宗教。求可能的最大宗教數（即連通分量數）。

並查集解法

• 初始每個學生自成一集。
• 每對關係 (i, j) 執行 union(i, j)。
• 最終統計根節點個數（或維護計數器，每次成功合併 ans--）。

代碼實現

#include <cstdio>
#include <cstring>
const int MAXN = 50005;

int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) fa[y] = x;
}

int main() {
    int n, m, tc = 1;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        for (int i = 1; i <= n; ++i) fa[i] = i;
        for (int i = 0; i < m; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            unite(a, b);
        }
        int cnt = 0;
        for (int i = 1; i <= n; ++i) if (find(i) == i) ++cnt;
        printf("Case %d: %d\n", tc++, cnt);
    }
    return 0;
}

優化細節

• 路徑壓縮 find 保證準常數時間。
• 可選：按秩合併（維護 rank 或 size）進一步優化。
• 輸入量大，使用 scanf。

總結

並查集模板題，核心是動態維護連通分量數。應用場景：社交網絡圈子、電路連通性、圖的連通分量統計等。