算法讲解056 必备 并查集-上

来源：算法讲解056【必备】并查集-上　·　2026-10-21

依据：视频字幕 2000 字

一句话概括

并查集（Union-Find / Disjoint Set Union, DSU）维护一堆不相交集合，支持「查某元素属于哪个集合（find）」「判断两元素是否同集合（isSameSet）」「合并两集合（union）」三种操作，均摊复杂度接近 O(1)。

它解决什么问题

• 动态合并集合：不断把两个元素所在的集合合并，同时随时查询两个元素是否已经连通。
• 典型场景：无向图连通性判定、Kruskal 最小生成树、等价类划分、动态连通块计数。
• 关键点：只合并不拆分（可撤销/可持久化是进阶内容，本讲不涉及）。

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

• 集合的代表元：每个集合选一个元素当「代表」，两个元素代表相同 ⇔ 同属一个集合。find(x) 返回 x 所在集合的代表。
• 父子关系 / 树：用一棵树表示一个集合，树根就是代表元。每个节点只记自己的父亲 parent[x]，根的父亲指向自己。
• 初始化：一开始每个元素自成一个集合，parent[i] = i。
• 合并：把一棵树的根挂到另一棵树的根下面，两棵树就变成一棵。
• 路径压缩：find 时把沿途节点直接挂到根上，下次查就快。
• 按大小/按秩合并：小树挂到大树下面，避免树退化成链。

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

• 用树表示集合：只要两元素在同一棵树里，它们的根就相同。所以「是否同集合」= 「find 结果是否相等」，这是判定集合相等的充要条件。
• 合并只需改一个指针：把根 A 的父亲改成根 B，整棵 A 树的所有节点就都归到 B 树下了——不用搬任何元素，这正是哈希表/链表做不到 O(1) 合并的原因。
• 为什么路径压缩有效：find 一次会走一条从节点到根的路径，把这条路径上所有点直接连到根，之后这些点再 find 就是 O(1)。摊还分析（反阿克曼函数 α(n)）保证总代价极小。
• 为什么按大小合并有效：每次合并让小树的根挂到大树根下，任意节点的树高最多 O(log n)，再叠加路径压缩，实际几乎常数。
• 两者结合：单用路径压缩均摊 O(log n)（甚至接近 O(1)），单用按秩合并最坏 O(log n)，两者一起用均摊 O(α(n))，α(n) ≤ 4（n 在 1e6 以内），可视为常数。

步骤（编号，可照着写）

1. 初始化：parent[i] = i，size[i] = 1（按大小合并用）。
2. find(x)：若 parent[x] != x，递归/迭代找根；找到后把路径上节点都指向根（路径压缩）。
3. isSameSet(a, b)：find(a) == find(b)。
4. union(a, b)：

- 分别找根 ra = find(a), rb = find(b)；

- 若 ra == rb 直接返回（已同集合）；

- 比较 size[ra] 与 size[rb]，小根挂到大根下：parent[小] = 大，size[大] += size[小]。

1. 需要统计连通块数量时，维护一个计数器：初始为 n，每次成功合并减 1。

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

n = 5，元素 1..5，初始 parent = [1,2,3,4,5]，size = [1,1,1,1,1]，连通块数 = 5。

| 操作 | 说明 | parent 变化 | size 变化 | 连通块 |

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

| union(1,2) | 根 1、2，size 相等，2 挂 1 下 | parent[2]=1 | size[1]=2 | 4 |

| union(3,4) | 根 3、4，4 挂 3 下 | parent[4]=3 | size[3]=2 | 3 |

| union(2,3) | find(2)=1，find(3)=3，size[1]=2, size[3]=2，3 挂 1 下 | parent[3]=1 | size[1]=4 | 2 |

| isSameSet(4,5) | find(4)=1（路径 4→3→1 压缩为 4→1），find(5)=5，不等 | parent[4]=1 | — | 2 |

| union(4,5) | find(4)=1，find(5)=5，size[1]=4 > size[5]=1，5 挂 1 下 | parent[5]=1 | size[1]=5 | 1 |

最终所有元素根都是 1，连通块数 = 1。

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

Python（好读版）

class DSU:
    def __init__(self, n):
        # 下标 0..n-1
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n  # 连通块数量

    def find(self, x):
        # 迭代路径压缩，避免递归爆栈
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # 第二遍：把路径上所有点直接挂到根
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def is_same_set(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        # 按大小合并：小树挂大树
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

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

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

struct DSU {
    vector<int> parent, sz;
    int components;  // 连通块数量

    DSU() {}
    explicit DSU(int n) { init(n); }

    // 下标 0..n-1
    void init(int n) {
        parent.resize(n);
        sz.assign(n, 1);
        components = n;
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    // 迭代路径压缩（防爆栈，常数也小）
    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int nxt = parent[x];
            parent[x] = root;
            x = nxt;
        }
        return root;
    }

    bool isSameSet(int a, int b) { return find(a) == find(b); }

    // 返回是否真的合并了（原来不同集合）
    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);  // 小挂大
        parent[rb] = ra;
        sz[ra] += sz[rb];
        --components;
        return true;
    }
};

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

    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) dsu.unite(a, b);
        else cout << (dsu.isSameSet(a, b) ? "YES\n" : "NO\n");
    }
    return 0;
}

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

• 空间：O(n)，两个 int 数组（parent + size），1e6 元素约 8MB，很省。
• 时间（路径压缩 + 按大小合并）：

- 单次 find / union / isSameSet：均摊 O(α(n))，α(n) ≤ 4（n ≤ 1e6），实际就是常数。

- 最坏单次（不摊还）O(log n)，但摊还后极低。

- m 次操作总时间 O(m·α(n))，1e6 次操作轻松过。

• 常数：非常小，迭代 find + 数组访问，比递归 find 更快、更安全。1e6 级别完全无压力，2e6 也稳。

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

• 题面出现「连通」「是否属于同一组」「合并两个集合」「等价类」「朋友的朋友」。
• Kruskal 求 MST：按边权排序后依次 union，判断是否成环。
• 无向图动态加边 + 查询连通性（只加不删）。
• 连通块计数：每次成功 union 减一。
• 带条件合并：如「敌人的敌人是朋友」（种类并查集，下期内容）。
• 网格图中「岛屿数量」「连通区域」类问题（BFS/DFS 也能做，但并查集适合动态加边）。
• 看到「n 个点 m 条边，问至少加几条边使图连通」——答案 = 连通块数 − 1。

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

// 并查集模板：路径压缩 + 按大小合并
// 下标 0..n-1，若题目 1..n 请自行 -1 或把 init 改成 1..n
struct DSU {
    vector<int> parent, sz;
    int components;

    void init(int n) {
        parent.resize(n);
        sz.assign(n, 1);
        components = n;
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int nxt = parent[x];
            parent[x] = root;
            x = nxt;
        }
        return root;
    }

    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);
        parent[rb] = ra;
        sz[ra] += sz[rb];
        --components;
        return true;
    }

    bool isSameSet(int a, int b) { return find(a) == find(b); }
};

多测时每次 dsu.init(n) 即可（resize + assign 会重置，不会残留上一组数据）。

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

1. 下标从 0 还是 1：模板用 0..n-1；题目若给 1..n，读入后 --a; --b; 或 init(n+1) 用 1..n。混用必 WA。
2. 多测不清空：parent 和 sz 必须每组测试重新 init，否则残留上一组数据。用 init(n) 最稳。
3. 递归 find 爆栈：n 到 1e6 且树退化成链时递归 find 可能栈溢出（尤其没按秩合并时）。用迭代版。
4. 忘记路径压缩：只写 while(parent[x]!=x) x=parent[x]; return x; 不压缩，最坏 O(n) 单次，大数据 TLE。
5. union 时没比较 size 直接挂：可能退化成链，虽然路径压缩能救，但常数变大，最好按大小合并。
6. components 只在成功合并时减：ra == rb 时不能减，否则连通块数错。
7. isSameSet 写成比较 parent 而非根：必须 find(a)==find(b)，不能 parent[a]==parent[b]。
8. long long：并查集本身只用 int 下标，不需要 long long；但若在并查集外累加边权（如 Kruskal 求 MST 总权），那个累加变量要 long long。
9. Kruskal 里边权排序 + union 判环：union 返回 false 说明这条边会成环，跳过；返回 true 才计入 MST。
10. 网格题坐标映射：id = r * m + c，注意行列哪个是 m，别搞反。

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

• Kruskal MST：边按权排序，依次 unite(u,v)，成功则加入 MST 并累加权值，直到选了 n-1 条边。改法：在模板外加排序和累加。
• 连通块计数：直接用 components，或每次成功 union 后输出。
• 判断图是否连通：所有边 union 完后看 components == 1。
• 冗余连接（LeetCode 684）：依次 union，第一条 unite 返回 false 的边就是答案。
• 岛屿数量 II（动态加陆地）：每加一块陆地，先 components++，再和上下左右已存在的陆地 union（每次成功 union 再 components--）。
• 种类并查集 / 带权并查集：下期内容，本讲不展开。
• 可撤销并查集：不能用路径压缩（会破坏可撤销性），只用按秩合并，配合栈记录合并操作。进阶内容。

常见坑

• 用 map<int,int> 或 unordered_map 存 parent：常数巨大，1e5 以上必 TLE。必须用 vector/数组。
• 用 list 或 set 维护集合：合并要搬家，O(n) 每次，完全错误方向。
• 递归 find 在 1e6 数据上爆栈（Windows 栈小）。
• 多测忘记 init，第二组开始全错。
• components 初始值写成 0 或 n-1。
• 路径压缩写成「只压缩起点」而非整条路径（效果差但仍正确，只是慢）。
• 1..n 下标却 init(n) 导致下标 n 越界（应 init(n+1)）。

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

• 带权并查集：边带权（如距离、相对关系），find 时累加权值，可解「食物链」「奇偶性」类问题。
• 种类并查集：开 k 倍空间表示「x 属于第 i 类」，解「敌人/朋友」问题。
• 可撤销并查集：按秩合并 + 操作栈，用于线段树分治、离线动态连通性。
• 可持久化并查集：配合可持久化数组，查询历史版本连通性。
• 实际用途：编译器类型等价分析、图像连通区域标记、网络动态连通、社交网络好友圈。
• 面试常问：「并查集为什么接近 O(1)？」答：路径压缩 + 按秩合并，摊还 α(n)。「能删除吗？」答：普通并查集不支持删除，需可撤销或重建。

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

题 1：n=6，依次执行 union(1,2), union(3,4), union(2,3), union(5,6), union(4,5)（下标 1..6）。问最终连通块数和元素 1 所在集合的大小。