UVA 10608 Friends：並查集求最大朋友圈規模

問題描述

N 個人，M 對認識關係（無向邊）。朋友圈定義為連通分量。求最大朋友圈的人數。多測試用例，N ≤ 30000, M ≤ 500000。

並查集（Disjoint Set Union）

維護每個集合的代表元與大小：

• parent[x]：父節點，根節點 parent[x] == x
• size[x]：以 x 為根的集合大小（僅根節點有效）

核心操作

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 (size[a] < size[b]) swap(a, b); // 按秩合併
    parent[b] = a;
    size[a] += size[b];
}

算法流程

1. 初始化：parent[i]=i, size[i]=1
2. 讀入 M 條邊，調用 unite(x, y)
3. 遍歷 1..N，找根節點 find(i)==i，取最大 size[i]

完整代碼

#include 
#include 
using namespace std;
const int MAXN = 30005;
int parent[MAXN], sz[MAXN];

int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, M; scanf("%d%d", &N, &M);
        for (int i=1; i<=N; ++i) parent[i]=i, sz[i]=1;
        for (int i=0; i