并查集
普通并查集
- 并查集可以维护无向连通性，并支持动态加边；
- 并查集可以维护染色问题：每次操作给定两种颜色 \(a,b\)，将所有颜色为 \(a\) 的点染为 \(b\)；
int fa[N];
void init() {
for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
fa[find(y)] = find(x);
}
P4119 [Ynoi2018] 未来日记
见分块
YbtOj 沧海桑田
见题解
并查集优化
路径压缩
简洁，高效，常用，均摊复杂度
代码见上文
启发式合并
简洁，稍慢，非均摊
int fa[N], sz[N];
void init() {
for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}
int find(int x) {
if(fa[x] == x) return x;
return find(fa[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(sz[y] > sz[x]) swap(x, y);
fa[y] = x;
sz[x] += sz[y];
}
带权并查集
带权并查集通常用来维护带权连通性问题。
P1196 [NOI2002] 银河英雄传说
扩展域并查集
扩展域并查集通常用来维护动态 \(k\)-染色问题。