算法讲解057 必备 并查集-下

来源：算法讲解057【必备】并查集-下　·　2026-10-22

依据：视频字幕 2000 字

一句话概括

并查集（DSU）用“集合标签/集合属性”把同行同列、同属性、同连通块的元素合并，答案往往是 N - 集合个数 或“每个集合维护一个聚合量”。

它解决什么问题

• 元素之间只关心“是否属于同一类/同一连通块”，不关心具体路径。
• 需要动态合并两个集合，并查询集合大小、集合内最值、集合内元素个数等聚合信息。
• 典型题面：给若干点/石头/边，同行同列/有边相连就合并，问最多能删多少、最少剩多少、有多少连通块。

基础知识（前置概念，用大白话解释）

• 集合：一堆元素，只关心“在不在一起”。
• 代表元（根）：每个集合选一个“老大”，判断两个元素是否同集合，就看老大是不是同一个。
• 路径压缩：找老大时把沿途节点直接挂到老大下面，下次找得快。
• 按大小/按秩合并：合并时小集合挂到大集合下面，树高更矮。
• 集合标签/集合属性：每个集合额外维护一个值，比如集合大小 sz、集合内石头数、集合内最大行号等。合并时把两个标签合并。
• 坐标离散化/哈希表映射：坐标很大（如 1e4、1e9）但点数少（如 1e3、1e5），不能开 fa[1e9]，要用 unordered_map 或离散化把“行号/列号”映射成编号。

原理（为什么这么做是对的，尽量给直觉）

以“移除最多同行或同列石头”为例：

• 把每个石头看成一个点；如果两个石头同行或同列，就在它们之间连一条边。
• 一个连通块内，只要还有至少两个石头，就一定能通过“同行/同列”关系不断删到只剩 1 个。直觉：连通块像一张由横竖线段连起来的图，从叶子（边缘）开始删，每次删掉一个只连一条边的点，最后一定剩一个。
• 不同连通块之间没有任何同行/同列关系，互相删不掉。
• 所以：若有 k 个连通块，最多删到每个连通块剩 1 个，即剩 k 个，最多删除 N - k。

合并方式：不需要两两枚举石头。对每一行维护“这一行第一次出现的石头编号”，对每一列同理；新石头到来时，如果该行/列已有石头，就合并。这样每个石头最多触发两次合并。

步骤（编号，可照着写）

1. 读入 n 个石头，每个石头有 (x, y)。
2. 初始化并查集，fa[i] = i，sz[i] = 1，集合数 cnt = n。
3. 准备两个映射：rowFirst：行号 -> 该行第一个石头编号；colFirst：列号 -> 该列第一个石头编号。
4. 对每个石头 i：

- 若 rowFirst 中已有行号 x，设对方为 j，union(i, j)；否则 rowFirst[x] = i。

- 若 colFirst 中已有列号 y，设对方为 j，union(i, j)；否则 colFirst[y] = i。

1. 每次成功合并（两个不同集合）时 cnt--。
2. 答案：n - cnt（最多删除数），或 cnt（最少剩余数）。

样例（一个具体小例子，带每步变化）

石头：(0,0), (0,1), (1,1), (2,2)，n=4。

| 步骤 | 石头 | 行映射 | 列映射 | 合并 | cnt |

|---|---|---|---|---|---|

| 初始 | - | 空 | 空 | - | 4 |

| 1 | (0,0) | row[0]=0 | col[0]=0 | 无 | 4 |

| 2 | (0,1) | row[0]已有0 | col[1]=1 | union(1,0) | 3 |

| 3 | (1,1) | row[1]=2 | col[1]已有1 | union(2,1) | 2 |

| 4 | (2,2) | row[2]=3 | col[2]=3 | 无 | 2 |

最终 cnt=2，最多删除 4-2=2。两个连通块：{0,1,2} 和 {3}，各剩 1 个。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（好读版）

class DSU:
    def __init__(self, n):
        self.fa = list(range(n))
        self.sz = [1] * n
        self.cnt = n  # 集合个数

    def find(self, x):
        while self.fa[x] != x:
            self.fa[x] = self.fa[self.fa[x]]
            x = self.fa[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.sz[ra] < self.sz[rb]:
            ra, rb = rb, ra
        self.fa[rb] = ra
        self.sz[ra] += self.sz[rb]
        self.cnt -= 1
        return True


def remove_stones(stones):
    n = len(stones)
    dsu = DSU(n)
    row_first = {}
    col_first = {}
    for i, (x, y) in enumerate(stones):
        if x in row_first:
            dsu.union(i, row_first[x])
        else:
            row_first[x] = i
        if y in col_first:
            dsu.union(i, col_first[y])
        else:
            col_first[y] = i
    return n - dsu.cnt

C++（竞赛风，可直接抄）

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa, sz;
    int cnt; // 当前集合个数
    DSU(int n = 0) { init(n); }
    void init(int n) {
        fa.resize(n);
        sz.assign(n, 1);
        iota(fa.begin(), fa.end(), 0);
        cnt = n;
    }
    int find(int x) {
        while (fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        fa[rb] = ra;
        sz[ra] += sz[rb];
        --cnt;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];

    DSU dsu(n);
    unordered_map<int, int> rowFirst, colFirst;
    rowFirst.reserve(n * 2);
    colFirst.reserve(n * 2);

    for (int i = 0; i < n; ++i) {
        auto itR = rowFirst.find(x[i]);
        if (itR != rowFirst.end()) dsu.unite(i, itR->second);
        else rowFirst[x[i]] = i;

        auto itC = colFirst.find(y[i]);
        if (itC != colFirst.end()) dsu.unite(i, itC->second);
        else colFirst[y[i]] = i;
    }

    cout << n - dsu.cnt << '\n';
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 并查集：路径压缩 + 按大小合并，单次操作均摊 O(α(n))，近似常数。
• 本题：n 次 find/unite，总时间 O(n α(n))，哈希表平均 O(1)，最坏哈希冲突可退化，竞赛中通常可接受。
• 空间：O(n)。
• 常数：很小；vector + 数组式并查集比 map 快很多。

竞赛里什么时候用（看到什么题面特征就该想到它）

• “同行/同列/同属性就连在一起”“能删到最少剩几个”。
• “连通块个数”“合并后集合大小/最值”。
• 给边 (u,v) 表示合并，问最终有多少组、每组多少元素。
• 坐标很大但点数不多：需要 unordered_map 或离散化。
• 需要给集合打标签：集合内石头数、集合内最大权值、集合内是否含特殊点。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

struct DSU {
    vector<int> fa, sz;
    int cnt;
    DSU(int n = 0) { init(n); }
    void init(int n) {
        fa.resize(n);
        sz.assign(n, 1);
        iota(fa.begin(), fa.end(), 0);
        cnt = n;
    }
    int find(int x) {
        while (fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        fa[rb] = ra;
        sz[ra] += sz[rb];
        --cnt;
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
    int size(int x) { return sz[find(x)]; }
};

带集合标签的写法（例如集合内石头数、集合内最大行号）：

struct DSU {
    vector<int> fa, sz;
    vector<int> maxRow; // 集合标签示例
    int cnt;
    void init(int n, const vector<int>& row) {
        fa.resize(n); sz.assign(n, 1); maxRow = row;
        iota(fa.begin(), fa.end(), 0);
        cnt = n;
    }
    int find(int x) {
        while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
        return x;
    }
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (sz[ra] < sz[rb]) swap(ra, rb);
        fa[rb] = ra;
        sz[ra] += sz[rb];
        maxRow[ra] = max(maxRow[ra], maxRow[rb]); // 合并标签
        --cnt;
        return true;
    }
};

边界与易错点（WA 的常见原因，越具体越好）

• 坐标范围大：不能开 fa[1e9]，必须 unordered_map 或离散化。
• 多测清空：fa/sz/cnt/rowFirst/colFirst 每次都要重置；unordered_map 建议重新构造或 clear()。
• 下标从 0 还是 1：石头编号通常 0-based；如果题目 1-based，读入后减 1。
• 答案公式：是 n - 集合个数，不是 n - 1；空输入/n=0 要特判。
• 重复合并：同一行多个石头，只和“该行第一个”合并即可，不要两两合并导致复杂度爆炸。
• long long：答案 n - cnt 在 n 很大时仍可能超 int（若题目规模到 1e9 级别），但本题 n 通常 1e3~1e5，int 够；保险可用 long long 输出。
• 哈希表被卡：unordered_map<int,int> 在极端数据下可能被卡，竞赛可用 gp_hash_table 或离散化。
• 路径压缩写法：fa[x] = fa[fa[x]] 是路径减半，正确；不要写成 fa[x] = x。
• 按大小合并方向：小挂大，别反了，否则树高退化。

同类题 / 变形（说清楚怎么改）

• 连通块个数：直接输出 dsu.cnt。
• 每个连通块大小：合并后遍历 i，sz[find(i)]。
• 集合内最值/特殊标记：在 unite 里合并标签，如 maxRow[ra] = max(maxRow[ra], maxRow[rb])。
• 带权并查集（视频提到后续）：边上有权值，维护到根的距离/异或和，find 时累加。
• 可撤销并查集（视频提到后续）：不能路径压缩，用按秩合并 + 栈记录合并操作，支持回滚。
• 可持久化并查集（视频提到后续）：用主席树维护 fa，支持历史版本查询。
• 网格连通块：把二维坐标压成一维编号，四方向合并。

常见坑

• 用 map 存行/列映射，常数大，1e5 可能 TLE；优先 unordered_map 或离散化后数组。
• 多测时 unordered_map 没清空，上一组数据污染下一组。
• find 递归写法在链很长时爆栈；竞赛用迭代路径减半。
• 合并时忘记 --cnt，答案偏大。
• 只合并行不合并列，或只合并列不合并行，连通块数算多。
• 坐标相同但石头编号不同，别把“同一行第一个”覆盖成最后一个，否则合并关系仍对但逻辑要一致。

拓展（变体、实际用途、面试常问）

• 实际用途：网络连通性、社交网络好友圈、图像连通区域、Kruskal 最小生成树、等式约束满足性。
• 面试常问：并查集复杂度为什么近似 O(1)（阿克曼反函数）；路径压缩和按秩合并能否只用一个；如何支持删除（可撤销并查集/离线倒序）。
• 变体：带权并查集（食物链、奇偶校验）、可撤销并查集（线段树分治）、可持久化并查集（历史版本连通性）。
• 标签技巧：集合维护 sum/max/min/count，合并时按需合并，是很多“集合属性”题的核心。

自测 3 题（题目 + 折叠答案）

题 1：n=3 个石头 (0,0),(0,0),(1,1)，最多删除几个？