并查集实现
路径压缩 + 按大小合并的并查集实现,含调用示例和实现细节。时间 O(alpha(n)) 均摊,空间 O(n) · 标签 数据结构 / 并查集 / 实现
使用约定
- 元素用 0-index 编号;1-index 时构造
DSU dsu(n + 1)。 find(x)返回代表元。unite(a, b)返回是否真的发生了合并;已经在同一集合时返回false。size(x)返回 所在集合的大小。
实现
struct DSU {
vector<int> fa, sz;
explicit DSU(int n) : fa(n), sz(n, 1) {
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
fa[b] = a;
sz[a] += sz[b];
return true;
}
int size(int x) {
return sz[find(x)];
}
};调用示例
统计无向图的连通分量数量:
DSU dsu(n);
int components = n;
for (auto [u, v] : edges) {
if (dsu.unite(u, v)) --components;
}
cout << components << '\n';实现细节
fa初始化成自身;sz初始化成 1。find使用路径压缩:fa[x] = find(fa[x])。- 合并时按大小把较小的树挂到较大的树下。
sz只在根节点有意义,size(x)要先find(x)。- 自环或重复边调用
unite会返回false,不会改变任何集合。 - 递归
find在极端情况下可能很深;路径压缩后一般没问题,必要时改迭代。 - 标准并查集不支持删除;需要回滚时用可撤销并查集。
复杂度
| 操作 | 均摊复杂度 | 说明 |
| find | 路径压缩 | |
| unite | 两次 find + 按大小合并 | |
| 空间 | fa 与 sz |
其中 是反阿克曼函数,实际可视为常数。
对应例题
- 洛谷 P3367:【模板】并查集
- 洛谷 P1551:亲戚
- 洛谷 P3958:奶酪(连通性判断)
- 洛谷 P2024:[NOI2001] 食物链(扩展域 / 带权并查集)
- 洛谷 P1197:[JSOI2008] 星球大战(逆向加边)