POJ 1611 The Suspects：並查集快速統計 SARS 接觸者

問題描述

NSYSU 有 n 個學生（0~n-1），m 個學生組。規則：若一組中有嫌疑人，全組都是嫌疑人。初始 0 號為嫌疑人。給定組員名單，求最終嫌疑人數。

輸入多組測試，n ≤ 30000, m ≤ 500。每組第一行 k 及 k 個學生號。n=m=0 結束。

核心思路：並查集

學生之間的「同組」關係具有傳遞性，天然形成不相交集合。0 號所在集合的大小即為答案。

• 初始化：每個學生自成一集，秩（大小）為 1。
• 合併：讀入每組，將第一個成員與其餘成員 union。
• 查詢：find(0) 找到根，輸出該根的秩。

優化技巧

• 路徑壓縮：find 時將節點直接指向根，攤還 O(α(n))。
• 按秩合併：小樹掛大樹根下，保證樹高極低。
• 只需維護根節點的 size（秩），合併時累加。

代碼實現 (C++)

#include <cstdio>
#include <cstring>
const int MAXN = 30010;
int parent[MAXN], sz[MAXN];
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
}
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        for (int i = 0; i < n; ++i) { parent[i] = i; sz[i] = 1; }
        for (int i = 0; i < m; ++i) {
            int k, first; scanf("%d%d", &k, &first);
            for (int j = 1; j < k; ++j) {
                int x; scanf("%d", &x);
                unite(first, x);
            }
        }
        printf("%d\n", sz[find(0)]);
    }
    return 0;
}

複雜度

• 時間：O((n + 總成員數) α(n)) ≈ 線性。
• 空間：O(n)。

關鍵點

• 題目本質是動態連通性，並查集是標準解法。
• 注意輸入格式：每組第一個數是 k，接著 k 個學生號。
• 只需輸出 0 所在集合大小，無需遍歷所有學生。

這道題是並查集入門級應用，清晰展示了「等價關係合併 + 根節點信息維護」的模式。