【題目敘述】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;
}