POJ 1611 The Suspects - 並查集傳染病傳播

問題描述

學生分組，同組視為密切接觸。學生 0 為疑似感染者。若一組中有疑似，全組標記為疑似。求最終疑似人數。多組測試，n≤30000, m≤500。

並查集建模

每個學生為一個節點。同組學生合併到同一集合。最後統計與 0 同集合的學生數。並查集支持路徑壓縮和按秩合併，近乎 O(1) 操作。

代碼實現（C++）

#include 
#include 
using namespace std;

struct DSU {
    vector parent, rank;
    DSU(int n) : parent(n), rank(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        DSU dsu(n);
        for (int i = 0; i < m; i++) {
            int k; cin >> k;
            if (k == 0) continue;
            int first; cin >> first;
            for (int j = 1; j < k; j++) {
                int x; cin >> x;
                dsu.unite(first, x);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) if (dsu.same(i, 0)) cnt++;
        cout << cnt << '\n';
    }
    return 0;
}

複雜度

時間 O((n + 總成員數) * α(n))，空間 O(n)。完全滿足限制。