HDU 1856 More is Better：並查集求最大連通分量

題目大意

有 1000 萬個男孩（編號 1~10⁷），給出 n (≤10⁵) 對直接好友關係。好友關係具有傳遞性（A-B, B-C ⇒ A-C）。選擇一個最大的群體，使群體內任意兩人直接或間接為好友。輸出最大群體人數。

解題思路

經典並查集應用：

1. 每個男孩初始各自為一個集合
2. 遍歷所有好友對，執行 `union` 合併集合
3. 維護 `size[root]` 記錄每個集合大小
4. 最後遍歷所有根節點，找出最大 `size`

關鍵代碼

const int MAXN = 10000005; // 題目上限 10^7，但實際只需映射出現的節點
int fa[MAXN], sz[MAXN];

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

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) {
        fa[a] = b;
        sz[b] += sz[a];
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        // 僅初始化出現的節點（或用 map 映射壓縮座標）
        // 這裡簡化：假設節點號 ≤ 1000000
        int max_id = 0;
        vector> edges(n);
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &edges[i].first, &edges[i].second);
            max_id = max(max_id, max(edges[i].first, edges[i].second));
        }
        for (int i = 1; i <= max_id; ++i) {
            fa[i] = i; sz[i] = 1;
        }
        for (auto &e : edges) unite(e.first, e.second);
        int ans = 0;
        for (int i = 1; i <= max_id; ++i)
            if (fa[i] == i) ans = max(ans, sz[i]);
        printf("%d\n", ans);
    }
}

優化要點

• 座標壓縮：節點編號高達 10⁷，但實際出現 ≤ 2×10⁵，用 `unordered_map` 映射到連續索引，大幅節省內存
• 路徑壓縮 + 按秩合併：保證近乎 O(1) 操作
• 輸入優化：大數據量下使用 `scanf` 或快速 IO

複雜度

• 時間：O(n α(n))，n 為好友對數
• 空間：O(m)，m 為實際出現的不同男孩數

樣例解析

// 輸入1：
4
1 2
3 4
5 6
1 6
// 集合：{1,2,5,6} size=4, {3,4} size=2 → 輸出 4

// 輸入2：
4
1 2
3 4
5 6
7 8
// 四個 size=2 集合 → 輸出 2