博客详情 - oirush

admin 的博客
并查集 (DSU)
admin SU @ 2026-6-7 19:54:02

一、算法概述

并查集（Disjoint Set Union, DSU）也叫 Union-Find 数据结构，是一种用来管理不相交集合的数据结构。它支持两种核心操作：

Find（查找）： 确定某个元素属于哪个集合（找到该集合的代表元素/根节点）
Union（合并）： 将两个不相交的集合合并为一个集合

并查集最初每个元素各自构成一个集合，随着 Union 操作的进行，集合逐渐合并，最终可以在近似 O(1) 的时间内判断两个元素是否属于同一集合。

二、核心思想

数据结构

每个集合用一棵树来表示，树的根节点是这个集合的代表元素。使用一个 parent[] 数组，parent[i] 指向节点 i 的父节点。初始时每个节点指向自己：parent[i] = i。

两大优化

1. 路径压缩（Path Compression）：

在 Find(x) 过程中，将查找路径上的所有节点直接连接到根节点。这使得树变得非常扁平，后续查找更快。

Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])    // 递归压缩路径
    return parent[x]

2. 按秩合并（Union by Rank / Size）：

在合并两个集合时，总是将较小的树（秩较小或节点数较少）的根连接到较大的树的根上，避免树退化成链。

Union(x, y):
    rootX = Find(x), rootY = Find(y)
    if rootX != rootY:
        if rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX]++

三、算法步骤 / 伪代码

初始化:
    parent[i] = i      (每个节点的父节点是自己)
    rank[i] = 0        (每个节点的初始秩为 0)

Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])    // 路径压缩
    return parent[x]

Union(x, y):
    rootX = Find(x)
    rootY = Find(y)
    if rootX == rootY:
        return                          // 已经在同一集合中
    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY           // 小的连接到大的
    else if rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    else:
        parent[rootY] = rootX           // 秩相同，任意连接，秩+1
        rank[rootX]++

IsConnected(x, y):
    return Find(x) == Find(y)

四、C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

class DSU {
public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        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 所在的集合（按秩合并）
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;  // 已经在同一集合中

        // 按秩合并：秩小的树连到秩大的树上
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // 判断 x 和 y 是否在同一集合中
    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    // 统计有多少个不相交集合
    int countSets() {
        int cnt = 0;
        for (int i = 0; i < (int)parent.size(); i++) {
            if (parent[i] == i) cnt++;
        }
        return cnt;
    }

    // 打印每个节点的父节点和根节点（调试用）
    void print(int n) {
        cout << "节点:  ";
        for (int i = 0; i < n; i++) printf("%2d ", i);
        cout << "\n根:    ";
        for (int i = 0; i < n; i++) printf("%2d ", find(i));
        cout << "\n秩:    ";
        for (int i = 0; i < n; i++) printf("%2d ", rank[i]);
        cout << endl;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

int main() {
    cout << "====== 并查集演示 ======" << endl;
    cout << "请输入元素个数: ";
    int n;
    cin >> n;

    DSU dsu(n);
    cout << "初始集合数: " << dsu.countSets() << endl;
    dsu.print(n);

    cout << "\n请输入操作次数: ";
    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        cout << "\n操作 " << (i + 1) << ": 输入类型 (1=合并, 2=查询是否连通, 3=集合数): ";
        int op;
        cin >> op;

        if (op == 1) {
            int x, y;
            cout << "  输入两个要合并的元素: ";
            cin >> x >> y;
            dsu.unite(x, y);
            cout << "  合并 " << x << " 和 " << y << " 完成" << endl;
            cout << "  当前集合数: " << dsu.countSets() << endl;
            dsu.print(n);
        } else if (op == 2) {
            int x, y;
            cout << "  输入两个要查询的元素: ";
            cin >> x >> y;
            if (dsu.connected(x, y))
                cout << "  " << x << " 和 " << y << " 在同一集合中" << endl;
            else
                cout << "  " << x << " 和 " << y << " 不在同一集合中" << endl;
        } else if (op == 3) {
            cout << "  当前集合数: " << dsu.countSets() << endl;
        }
    }

    return 0;
}

五、复杂度分析

操作	时间复杂度	说明
Find（带路径压缩）	近似 O(1)	严格来说是 O(α(n))，α 是阿克曼函数的反函数
Union（带按秩合并）	近似 O(1)	同上，α(n) 在实际范围内 ≤ 5
初始化	O(n)	初始化 n 个元素

阿克曼函数反函数 α(n)： 对任何实际应用中可能出现的 n（包括宇宙原子数），α(n) ≤ 5。因此并查集的单次操作可以认为是均摊常数时间。

若无优化（只用一个 parent 数组）：

Find 最坏 O(n)（退化成链表）
Union 最坏 O(n)

六、应用场景

判断图的连通性： 给定若干条边，判断任意两点是否连通
检测无向图中的环： 添加边时若两端点已在同一集合，则存在环
Kruskal 最小生成树算法： 核心依赖并查集来判断是否形成环
朋友圈 / 省份数量问题： 给定朋友关系矩阵，求连通分量数（LeetCode 547）
等价类合并： 等式方程的可满足性（LeetCode 990）
岛屿数量问题： 将相邻陆地合并（可用 BFS/DFS 替代）
网络连接恢复： 动态连通性问题
最近公共祖先（LCA）的 Tarjan 离线算法： 需要并查集支持

七、经典例题

LeetCode 547. 省份数量（朋友圈）

题目描述： 有 n 个城市，其中一些彼此相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n×n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，返回矩阵中省份的数量。

并查集解法：

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        DSU dsu(n);

        // 遍历上三角矩阵，连通的关系进行合并
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    dsu.unite(i, j);
                }
            }
        }

        // 统计根的数量，即省份数量
        return dsu.countSets();
    }

    class DSU {
    public:
        vector<int> parent, rank;
        DSU(int n) {
            parent.resize(n);
            rank.resize(n, 0);
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }

        void unite(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return;
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[rx] > rank[ry]) parent[ry] = rx;
            else { parent[ry] = rx; rank[rx]++; }
        }

        int countSets() {
            int cnt = 0;
            for (int i = 0; i < parent.size(); i++)
                if (parent[i] == i) cnt++;
            return cnt;
        }
    };
};

LeetCode 990. 等式方程的可满足性

题目描述： 给定一个由字符串方程组成的数组，每个方程 equations[i] 长度为 4，形式为 "a==b" 或 "a!=b"。判断是否存在整数赋值使得所有方程同时成立。

思路： 先处理所有 == 关系建立并查集，再检查所有 != 关系是否冲突。

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        DSU dsu(26);  // 26 个小写字母

        // 第一遍：处理所有相等关系
        for (auto& eq : equations) {
            if (eq[1] == '=') {
                dsu.unite(eq[0] - 'a', eq[3] - 'a');
            }
        }

        // 第二遍：检查所有不等关系是否与相等关系冲突
        for (auto& eq : equations) {
            if (eq[1] == '!') {
                if (dsu.connected(eq[0] - 'a', eq[3] - 'a'))
                    return false;
            }
        }
        return true;
    }
    // DSU 实现同上，省略
};

LeetCode 684. 冗余连接

题目描述： 给定一棵树加上一条额外边组成的图，找到这条冗余边（若有多个答案，返回最后出现的那个）。

思路： 遍历每条边，若两端点已在同一集合，则该边是冗余边。

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        DSU dsu(n + 1);

        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (dsu.connected(u, v)) {
                return edge;  // 这条边形成环
            }
            dsu.unite(u, v);
        }
        return {};
    }
};

并查集 (DSU)

一、算法概述

二、核心思想

数据结构

两大优化

三、算法步骤 / 伪代码

四、C++ 代码实现

五、复杂度分析

六、应用场景

七、经典例题

LeetCode 547. 省份数量（朋友圈）

LeetCode 990. 等式方程的可满足性

LeetCode 684. 冗余连接

状态

开发

支持

关于

并查集 (DSU)

一、算法概述

二、核心思想

数据结构

两大优化

三、算法步骤 / 伪代码

四、C++ 代码实现

五、复杂度分析

六、应用场景

七、经典例题

LeetCode 547. 省份数量（朋友圈）

LeetCode 990. 等式方程的可满足性

LeetCode 684. 冗余连接

状态

开发

支持

关于

还没有账户？

登录