当前位置：首页 > news >正文

[leetcode] C++ 并查集模板

news 2025/7/7 9:47:23

好的，这里为你提供一个功能齐全、经过优化的C++并查集（Disjoint Set Union, DSU）代码框架，特别适合在 LeetCode 等算法竞赛平台上使用。

这个模板包含了最重要的两个优化：路径压缩 (Path Compression) 和 按大小合并 (Union by Size)，这使得 find 和 unite 操作的平均时间复杂度接近 O(1)。

为什么选择这个模板？

高效性: 结合了路径压缩和按大小合并，性能极佳。
功能全面: 提供了 unite (合并), find (查找根节点), isConnected (判断连通性), getCount (获取连通分量数量), getSize (获取指定集合大小) 等常用接口。
封装性好: 使用 class 封装，在 LeetCode 的 Solution 类中可以直接作为成员或在函数内部实例化，代码清晰。
易于理解: 代码注释清晰，解释了每个部分的作用。

推荐模板：带路径压缩和按大小合并的并查集

这是最推荐的版本，在绝大多数情况下都应该使用它。

#include <vector>
#include <numeric> // 用于 std::iotaclass UnionFind {
private:// parent[i] 表示元素 i 的父节点std::vector<int> parent;// size[i] 表示以 i 为根的集合的大小（只在 i 是根节点时有意义）std::vector<int> size;// 记录连通分量的数量int count;public:// 构造函数：初始化 n 个元素的并查集UnionFind(int n) {count = n;parent.resize(n);// std::iota 是一个方便的函数，用 0, 1, 2, ... 来填充容器std::iota(parent.begin(), parent.end(), 0); // 每个集合初始大小都为 1size.assign(n, 1);}// 查找元素 x 的根节点（带路径压缩）int find(int x) {// 如果 x 的父节点不是它自己，说明 x 不是根节点if (parent[x] != 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) {// 按大小合并：将小集合合并到大集合中if (size[rootX] < size[rootY]) {std::swap(rootX, rootY); // 确保 rootX 是较大集合的根}// 将小集合的根(rootY)指向大集合的根(rootX)parent[rootY] = rootX;// 更新大集合的大小size[rootX] += size[rootY];// 连通分量数量减一count--;}}// 检查两个元素是否在同一个集合中bool isConnected(int x, int y) {return find(x) == find(y);}// 返回当前连通分量的数量int getCount() const {return count;}// 返回元素 x 所在集合的大小int getSize(int x) {return size[find(x)];}
};

如何在 LeetCode 中使用

假设题目是 547. 省份数量，这道题是并查集的经典应用。

题目描述：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与 b 直接相连，b 与 c 直接相连，那么 a 与 c 间接相连。省份是一组直接或间接相连的城市，组内任意两座城市之间都存在一条路径，而组外任意城市与组内任意城市均不相连。给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回省份的总数。

解题代码:

#include <vector>
#include <numeric>// 把上面那个 UnionFind 类的代码粘贴到这里class Solution {
public:int findCircleNum(std::vector<std::vector<int>>& isConnected) {int n = isConnected.size();if (n == 0) {return 0;}// 1. 初始化并查集UnionFind uf(n);// 2. 遍历邻接矩阵，合并城市// 只需要遍历上三角或下三角矩阵，因为 isConnected[i][j] == isConnected[j][i]for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (isConnected[i][j] == 1) {uf.unite(i, j);}}}// 3. 返回最终的连通分量数量return uf.getCount();}
};

基础模板：仅带路径压缩

如果你刚开始学习，可以先看这个更简单的版本，它只包含路径压缩，没有按大小合并。性能稍差，但在数据规模不大的情况下也够用。

class UnionFindBasic {
private:std::vector<int> parent;int count;public:UnionFindBasic(int n) {count = n;parent.resize(n);std::iota(parent.begin(), parent.end(), 0);}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}void unite(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY; // 简单合并count--;}}int getCount() const {return count;}
};

总结

特性	推荐模板 (路径压缩 + 按大小合并)	基础模板 (仅路径压缩)
时间复杂度	`find` 和 `unite` 操作接近 O(1) (严格来说是 O(α(n)))	`find` 和 `unite` 操作最坏为 O(log n)
空间复杂度	O(n)	O(n)
适用场景	所有场景，特别是数据规模大或性能要求高时	学习理解，或数据规模非常小