并查集
普通并查集：
路径压缩写法：
struct Union_Find_Set {
int f[N];
inline void init() {
for(int i = 1 ; i <= n ; ++ i)
f[i] = i;
}
inline int find(int x) {
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
inline void merge(int a, int b) {
int x = find(a), y = find(b);
f[y] = f[x];
}
} Set;
启发式合并写法：
struct Union_Find_Set {
int f[N], h[N];
inline void init() {
for(int i = 1 ; i <= n ; ++ i)
f[i] = i, h[i] = 1;
}
inline int find(int x) {
if(x != f[x]) return find(f[x]);
return f[x];
}
inline void merge(int a, int b) {
int x = find(a), y = find(b);
if(h[x] > h[y]) f[y] = f[x];
else {
f[x] = f[y];
if(h[x] == h[y]) ++ h[y];
}
}
} Set;
这是按秩合并的，当然也可以按元素个数启发式合并。
这俩可以写一起：
struct Union_Find_Set {
int f[N], h[N];
inline void init() {
for(int i = 1 ; i <= n ; ++ i)
f[i] = i, h[i] = 1;
}
inline int find(int x) {
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
inline void merge(int a, int b) {
int x = find(a), y = find(b);
if(h[x] > h[y]) f[y] = f[x];
else {
f[x] = f[y];
if(h[x] == h[y]) ++ h[y];
}
}
} Set;
要注意的是 find 里面的 if 写 return 的复杂度是假的。
例题
多而且杂，一般可用并查集维护的性质很突出。
CF217A Ice Skating
很傻逼的网格图问题。
同列 / 同行放到一个连通块里面，并查集轻松维护。
P2658 汽车拉力比赛
有点傻逼的网格图问题。
分析：
1.由于题目要求保证所有路标相互可达，于是想到并查集
2.发现对于任意一个 \(D\)，模拟一次都是 \(O(nm)\) 的，且 \(D\) 越大所有路标越可能相互可达，考虑二分 \(D\)
3.每次扫网格图，对于每个点，若和其相邻点高度差小于当前二分的 \(D\) 则连边，最后判断所有路标是否在一个连通块内
4.坐标 \((x, y)\) 可以改写成 \((x - 1)m + y\)
时间复杂度 \(O(nm\log V)\)，其中 \(V\) 为值域。
check 部分代码：
inline bool check(int x) {
init();
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j) {
//to(i, j) 为坐标的转换函数。
int pos = to(i, j), pos1 = to(i + 1, j), pos2 = to(i, j + 1);
if(i + 1 <= n && abs(a[pos] - a[pos1]) <= x) merge(pos, pos1);
if(j + 1 <= m && abs(a[pos] - a[pos2]) <= x) merge(pos, pos2);
}
int Fa = 0;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= m ; ++ j)
if(vis[to(i, j)]) {
if(! Fa) Fa = find(to(i, j));
else if(Fa != find(to(i, j))) return false;
}
return true;
}
扩展域并查集：
应用于有多个集合且有关系时。
另外这东西还能判二分图。
具体的就是建多个并查集。
带权并查集：
维护边的时候带权。
一般用路径压缩能够减少维护的信息。
合并时候的权值更新可以用向量去理解。
struct Union_Find_Set {
int f[N], val[N];
inline void init() {
memset(val, 0, sizeof val);
for(int i = 1 ; i <= n ; ++ i)
f[i] = i;
}
inline int find(int x) {
if(x != f[x]) val[x] += val[f[x]], f[x] = find(f[x]);
return f[x];
}
inline void merge(int a, int b, int Val) {
int x = find(a), y = find(b);
f[y] = f[x], val[y] = -val[a] + Val + val[b];
}
} Set;
当然操作不仅限于加法。
可撤销并查集
按加入的时间从后往前撤销。
用启发式合并写法实现（路径压缩改变树的形态），同时维护上述操作可以用栈来实现。
那么对于一条边为什么一定要是有顺序的撤销呢？如果不是按出栈的顺序撤销，那么必定有比他晚一些连边的集合的大小没法维护，所以必须按出栈顺序撤销。
struct Union_Find_Set {
int f[N], h[N];
stack<int> s;
inline void init() {
memset(val, 0, sizeof val);
for(int i = 1 ; i <= n ; ++ i)
f[i] = i, h[i] = 1;
}
inline int find(int x) {
if(x != f[x]) return find(f[x]);
return f[x];
}
inline void merge(int a, int b) {
int x = find(a), y = find(b);
if(h[x] > h[y]) f[y] = f[x];
else {
f[x] = f[y];
if(h[x] == h[y]) ++ h[y];
}
}
inline void Delete() {
if(s.empty()) return;
int k = s.top(); s.pop();
h[f[k]] -= h[k], f[k] = k;
}
inline void revoke(int x) {while(s.size() > x) Delete();}
} Set;