HDU More is Better：並查集求最大朋友圈規模

題目轉化

10⁷ 個男孩，給定 n 對直接好友關係。好友具有傳遞性（A-B, B-C ⇒ A-C）。求最大連通分量大小（即最大朋友圈人數）。

並查集核心實現與易錯點

錯誤版本分析：合併時僅更新 num[x] = num[x] + num[y]，未同步更新根節點計數，導致路徑壓縮後統計錯誤。

正確版關鍵修正

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        // 關鍵：將計數累加到新根節點
        num[ry] += num[rx];  // 或 num[rx] += num[ry]
        num[rx] = num[ry];   // 同步另一邊（可選，視查找邏輯）
        if (num[ry] > Max) Max = num[ry];
        // 按秩合併或任意合併
        if (rx > ry) father[rx] = ry;
        else father[ry] = rx;
    }
}

完整 AC 代碼

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 10000010;
int father[MAXN], num[MAXN], Max;

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

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx != ry) {
        num[ry] += num[rx];
        num[rx] = num[ry];
        if (num[ry] > Max) Max = num[ry];
        if (rx > ry) father[rx] = ry;
        else father[ry] = rx;
    }
}

void init() {
    for (int i = 1; i <= 10000000; i++) {
        father[i] = i;
        num[i] = 1;
    }
    Max = 1;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        init();
        while (n--) {
            int x, y; scanf("%d%d", &x, &y);
            merge(x, y);
        }
        printf("%d\n", Max);
    }
    return 0;
}

優化建議

• 路徑壓縮：find 中的遞歸賦值
• 按秩合併：維護 rank 陣列，小樹掛大樹
• 動態初始化：僅初始化出現過的節點（用 unordered_map），節省記憶體

本題是並查集維護連通分量大小的經典應用，關鍵在於正確維護根節點的尺寸計數。