【題解】POJ 1611 The Suspects

【題目敘述】https://vjudge.net/problem/POJ-1611
【解題想法】並查集,Disjoint Set Union-Find algorithm (DSU)

  • p[ ]:所屬集合的代表元素,同時代表集合的成員人數(負值表示),初始值設為 -1。(Line-18, Line-32)
  • 函式 Find( ):找出所屬集合的代表元素,同時壓縮路徑。
  • Line-28/29:執行並查集的 Union( ),把兩個集合的成員人數加起來。
#include <iostream>
#include <cstring>
using namespace std;

int n, m, p[30005], k, a, b;

int Find(int x){
    if (p[x] < 0) return x;
    else {
        p[x] = Find(p[x]);
        return p[x];
    }
}

int main() {
    while (cin >> n >> m){
        if (n == 0) break;
        memset(p, -1, sizeof(p));
        for (int i = 0; i < m; i++){
            cin >> k;
            cin >> a;
            if (k <= 1) continue;
            int ga = Find(a);
            for (int j = 1; j < k; j++){
                cin >> b;
                int gb = Find(b);
                if (ga == gb) continue;
                p[ga] += p[gb];
                p[gb] = ga;
            }
        }
        cout << -p[Find(0)] << "\n";
    }
    return 0;
}
分享本文 Share with friends