POJ 1838 區域最大點數：並查集合併相鄰點求前 K 大連通分量

問題轉化

平面上給定若干點。若兩點在水平或垂直方向相鄰（曼哈頓距離 = 1），則屬同一區域（連通分量）。求最大的 K 個區域的點數之和。K 不超過區域總數。

並查集解法

1. 初始化：每點自成一集，parent[i]=i，size[i]=1。
2. 合併水平相鄰：按 x 分組，組內按 y 排序；相鄰 y 差 1 的點合併。
3. 合併垂直相鄰：按 y 分組，組內按 x 排序；相鄰 x 差 1 的點合併。
4. 路徑壓縮 + 按秩合併：保證近乎 O(1) 操作。
5. 統計：遍歷所有點，找根節點，累加 size[root]（或直接用根節點的 size）。
6. 選 Top-K：將所有根節點的 size 收集，降序排序，取前 K 個求和。

關鍵數據結構

struct DSU {
    vector<int> p, sz;
    DSU(int n): p(n), sz(n,1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a, int b) {
        a=find(a); b=find(b); if(a==b) return;
        if(sz[a]

複雜度

排序 O(N log N)
並查集操作 O(N α(N)) ≈ O(N)
總時間 O(N log N)，空間 O(N)


實現細節

點坐標範圍未給，建議離散化或用哈希映射 (x,y) -> id。
輸入可能多測試用例，直到 EOF。
K 可能較大，用 nth_element 或部分排序優化 Top-K 選擇。


相關題目延伸

HDU 1213 / POJ 1988 / UVA 10147 — 經典並查集應用。
二維網格連通分量：DFS/BFS 同理，但並查集更適合動態添加點場景。