SDUT Ubiquitous Religions：並查集統計宗教派別上限

問題描述

大學有 n 名學生 (n ≤ 50000)，m 對學生確認信仰同一宗教。每生最多信一教。求可能的宗教派別**最大數量**（即連通分量數）。多測試用例，以 "0 0" 結束。

並查集解法

將「同教」關係建模為無向圖邊，連通分量即為一教。初始化 n 個單元素集合，處理 m 對合併操作，最後統計根節點個數。

代碼實現

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int father[100010], num[100010];

void Make_set(int n) {
    for (int i = 1; i <= n; i++) father[i] = i;
}

int Find(int x) {
    if (x != father[x]) father[x] = Find(father[x]); // 路徑壓縮
    return father[x];
}

void Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx == fy) return;
    father[fy] = fx;
}

int main() {
    int n, m, x, y, T = 1;
    while (~scanf("%d%d", &n, &m)) {
        if (!n && !m) break;
        memset(num, 0, sizeof(num));
        Make_set(n);
        while (m--) {
            scanf("%d%d", &x, &y);
            Union(x, y);
        }
        for (int i = 1; i <= n; i++) {
            int f = Find(i);
            num[f]++;
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) if (num[i]) cnt++;
        printf("Case %d: %d\n", T++, cnt);
    }
    return 0;
}

關鍵點

• 路徑壓縮 `Find` 保證近乎 O(1) 操作。
• 統計時需先 `Find(i)` 再計數，確保路徑壓縮生效，根節點計數準確。
• 數組大小開到 100010 避免越界。
• 輸出格式：`Case k: ans`，k 從 1 開始。

複雜度

• 時間：O((n + m) α(n))，極快。
• 空間：O(n)