并查集：原理、图解与 C++ 实战

一、什么是并查集

并查集（Disjoint Set Union，简称 DSU；也叫 Union-Find）是一种用于管理元素分组的数据结构。它主要支持两个操作：

• Find(x)：查询元素 x 属于哪个集合（返回该集合的代表元 / 根节点）
• Union(x, y)：把元素 x 和 y 所在的两个集合合并成一个

它的典型应用场景是动态连通性问题：在不断"添加连接"的过程中，快速回答"这两个点是否连通"。如果用朴素数组维护，单次查询是 O(n)；用并查集配合路径压缩，单次操作接近 O(1)。

1.1 三种常见实现对比

二、核心原理与图解

并查集的本质是用一棵树表示一个集合。每个节点有一个 parent 指针指向父节点，根节点的 parent 指向自己。判断两个元素是否同集合，只需看它们的根是否相同。

2.1 并查集的树形结构

2.2 find 与路径压缩

朴素的 find 是一路顺着 parent 往上找根。但若树退化成链，每次 find 都要 O(n)。路径压缩（Path Compression）的核心思想是：在 find 的过程中，把沿途所有节点直接挂到根下面，让树变得"扁平"。

2.3 union by rank（按秩合并）

合并两棵树时，如果把高的树挂到矮的树下，整体高度会增加；反之则不会。所以总是把矮树挂在高的树根下，这就是按秩合并。

2.4 复杂度分析

三、通用模板

下面是带路径压缩 + 按秩合并的完整并查集类，是面试和竞赛的标准写法，可以直接背下来套用：

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank_;   // rank_[i] 表示以 i 为根的树的高度估计
    int count;          // 当前连通分量个数

public:
    // 构造：每个元素自成一集合，parent 指向自己，rank 为 0
    UnionFind(int n) : parent(n), rank_(n, 0), count(n) {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    // 查找 x 的根，同时做路径压缩（沿途节点直接挂到根）
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // 递归压缩
        return parent[x];
    }

    // 合并 x 和 y 所在集合，返回是否真的合并了（原本就同集合则返回 false）
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // 已在同一集合

        // 按秩合并：矮树挂到高树下
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];  // 等高时合并后高度 +1

        --count;  // 连通分量数减 1
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    int getCount() const { return count; }
};

四、示例一：省份数量（LeetCode 547）

题目：有 n 个城市，其中一些彼此相连通。给定一个 n×n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连。省份是一组直接或间接相连的城市。返回省份的数量。

4.1 思路

每个城市初始自成一个集合。遍历矩阵的上三角（避免重复），若 isConnected[i][j] = 1，就 union(i, j)。最终连通分量数就是省份数量。

4.2 C++ 代码

#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }
};

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    UnionFind uf(n);
    // 只遍历上三角，避免重复合并
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1) uf.unite(i, j);
        }
    }
    // 统计根的个数（自己是自己 parent 的就是根）
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (uf.find(i) == i) ++ans;
    return ans;
}

五、示例二：账户合并（LeetCode 721）

题目：给定一个账户列表 accounts，每个账户包含一个名字和若干邮箱。如果两个账户有共同邮箱，则它们属于同一个人。合并属于同一个人的账户，返回合并后的账户列表（每个账户的邮箱按字典序升序排列）。

5.1 思路：把邮箱当节点

这题的难点在于合并的"实体"不是下标而是字符串邮箱。处理方法是：用哈希表把每个邮箱映射到一个下标，然后用并查集管理这些下标。同一账户内的所有邮箱两两 union（其实只要把第一个邮箱和其余的 union 即可）。

5.2 C++ 代码

#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
    }
};

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, int> emailToId;  // 邮箱 → 下标
    unordered_map<string, string> emailToName; // 邮箱 → 名字
    UnionFind uf(10000);  // 预留足够下标
    int id = 0;

    // 第一步：给每个邮箱分配 id，并把同一账户内的邮箱两两 union
    for (const auto& acc : accounts) {
        const string& name = acc[0];
        for (int i = 1; i < acc.size(); ++i) {
            const string& email = acc[i];
            if (!emailToId.count(email)) {
                emailToId[email] = id++;
                emailToName[email] = name;
            }
            // 把当前邮箱和账户第一个邮箱 union
            uf.unite(emailToId[acc[1]], emailToId[email]);
        }
    }

    // 第二步：按根邮箱分组收集所有邮箱
    map<string, vector<string>> groups;  // map 自动按 key 排序
    for (const auto& [email, idx] : emailToId) {
        string rootEmail;
        // 找根邮箱：通过 id 反查
        int rootId = uf.find(idx);
        for (const auto& [e, i] : emailToId)
            if (i == rootId) { rootEmail = e; break; }
        groups[rootEmail].push_back(email);
    }

    // 第三步：组装结果
    vector<vector<string>> ans;
    for (auto& [rootEmail, emails] : groups) {
        vector<string> account;
        account.push_back(emailToName[rootEmail]);
        sort(emails.begin(), emails.end());
        for (const auto& e : emails) account.push_back(e);
        ans.push_back(account);
    }
    return ans;
}

六、示例三：冗余连接（LeetCode 684）

题目：一棵树有 n 个节点（标号 1 到 n）和 n-1 条边。现在多加了一条边，使得图中恰好出现一个环。给定这 n 条边的列表，返回可以删去的那条边，使得剩下的图变成一棵树。如果有多个答案，返回输入中最后出现的那条。

6.1 思路：并查集判环

这是一道非常典型的并查集应用题。逐条加入边，每次 union 之前先 find 两端点：

• 如果两端点已经在同一集合——说明这条边是多余的（加上它会形成环），记录下来即可
• 否则——union 两端点

6.2 C++ 代码

#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // 已连通，加这条边会成环
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }
};

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();  // n 条边，n 个节点（标号 1..n）
    UnionFind uf(n + 1);  // 下标 1..n，多开一个

    for (const auto& e : edges) {
        int u = e[0], v = e[1];
        // 如果 u 和 v 已经在同一集合，这条边就是冗余的
        if (!uf.unite(u, v)) {
            return e;  // 题目保证恰好一个环，遇到即返回
        }
    }
    return {};  // 不会走到这里
}

七、总结与适用场景

典型题目清单

• LeetCode 547：省份数量（基础连通分量计数）
• LeetCode 200：岛屿数量（也可用并查集，但 DFS 更直观）
• LeetCode 684：冗余连接（判环）
• LeetCode 685：冗余连接 II（有向图版本，难度更大）
• LeetCode 721：账户合并（字符串映射 + 分组）
• LeetCode 737：句子相似性 II（传递闭包）
• LeetCode 990：等式方程的可满足性（先处理相等再处理不等）
• LeetCode 1319：连通网络的操作次数（连通分量数 - 1）
• Kruskal 最小生成树算法（按边权排序 + 并查集判环）