并查集
并查集是一种树型数据结构,其思想是用一个代表元(树根)去表示一个集合。通常用于处理不相交集合的合并及查询两点是否在同一个集合内。
路径压缩:有路径压缩就不需要按秩合并了,因为在压缩的过程中,会把当前点到根的这条链上的所有点都压缩掉。这样路径压缩总复杂度是O(n)。
按秩合并:启发式合并,如果不能路径压缩,可以通过按秩合并把树的高度控制在O(logn)的级别。
int par[maxn];
void init(int n) {
for (int i = 0; i < n; i++) par[i] = i;
}
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
par[x] = y;
}
带权并查集
带权指 子节点与父节点之间存在限制条件, 如子节点在父节点左边的x米处
接下来面临的两个难点:
- 路径压缩时权值的变化
- 两棵树合并时权值的变化
int find(int x){
if(x == par[x]) return x;
int fa = par[x];
par[x] = find(par[x]);
val[x] += val[fa];
return par[x];
}
删点
设要删的点为x,如果x是树的根,那么删除x之后,这棵树上的其他关系没有办法维持。我们可以通过给每个点都建立相应的虚拟父节点,比如1号点就连向1+n号点。之后每次合并的时候就用其虚拟父节点代替合并。删除点x的话可以将x直接指向一个新的节点,这样就能维持原来的关系。
int tot;
void init(int n) {
for (int i = 1; i <= n; i++) {
par[i] = i + n;
par[i + n] = i + n;
}
tot = 2 * n;
}
void remove(int x) {
par[x] = ++tot;
par[tot] = tot;
}
删边
将所有操作离线。
我们先把最后的状态建出来,然后逆着查询,这样原来的删边操作就变成了加边操作。
可撤销并查集
如果并查集想要支持回退操作,那么必然不能进行路径压缩。
所以只能通过按秩(高度)合并的方法来保证复杂度。
每次将一个版本(原树的根和原树的秩以及一些其它需要维护的东西)放进栈中,回退的时候从栈中一个一个复原。
struct UFS {
int par[maxn], h[maxn], top;
struct Node {
int x, y, fa, h;
Node(int x = 0, int y = 0, int fa = 0, int h = 0)
: x(x), y(y), fa(fa), h(h) {}
} stk[maxn];
void init(int n) {
top = 0;
for (int i = 1; i <= n; i++) par[i] = i, h[i] = 0;
}
int find(int x) { return x == par[x] ? x : find(par[x]); }
void merge(int u, int v) {
int x = find(u), y = find(v);
// if (x == y) return; 和回退的次数相关
if (h[x] > h[y]) swap(x, y);
stk[top++] = Node(x, y, par[x], h[y]);
if (h[x] == h[y]) h[y]++;
par[x] = y;
}
void undo(int k) {
for (int i = 0; i < k; i++) {
Node &it = stk[--top];
par[it.x] = it.fa;
h[it.y] = it.h;
}
}
} ufs;
可持久化并查集
这里用到了可持久化数组,但实际上就是主席树。可持久化数组可以做到修改和查询数组的历史版本,实际上就是用主席树中的叶子节点表示当前版本中此位置的值,可以参考例题P3919。
对于可持久化并查集,我们只要用主席树来维护par和dep的历史版本即可。注意可持久化并查集不能路径压缩,所以需要通过按秩合并来减小复杂度,因此需要维护一个深度数组dep。
find()
的复杂度是$O(\log^2 n)$,因为需要在主席树上查询。
参考例题P3402
#include <bits/stdc++.h>
using namespace std;
#define lson lch[k], l, m
#define rson rch[k], m + 1, r
const int maxn = 3e5 + 5;
const int N = maxn * 30;
int root[maxn], par[N], dep[N], lch[N], rch[N], dfn;
int n, m;
void build(int &k, int l, int r) {
k = ++dfn;
if (l == r) {
par[k] = l, dep[k] = 0;
return;
}
int m = l + r >> 1;
build(lson);
build(rson);
}
void update_par(int old, int &k, int l, int r, int p, int x) {
k = ++dfn;
if (l == r) {
par[k] = x;
dep[k] = dep[old];
return;
}
lch[k] = lch[old], rch[k] = rch[old];
int m = l + r >> 1;
if (p <= m)
update_par(lch[old], lson, p, x);
else
update_par(rch[old], rson, p, x);
}
void update_dep(int k, int l, int r, int p) {
if (l == r) {
dep[k]++;
return;
}
int m = l + r >> 1;
if (p <= m)
update_dep(lson, p);
else
update_dep(rson, p);
}
int query(int k, int l, int r, int p) {
if (l == r) return k;
int m = l + r >> 1;
if (p <= m)
return query(lson, p);
else
return query(rson, p);
}
int find(int k, int x) {
int u = query(k, 1, n, x);
if (par[u] == x) return u;
return find(k, par[u]);
}
void merge(int old, int &k, int x, int y) {
int posx = find(old, x), posy = find(old, y);
if (par[posx] == par[posy]) return;
if (dep[posx] > dep[posy]) swap(posx, posy);
update_par(old, k, 1, n, par[posx], par[posy]); // !
if (dep[posx] == dep[posy]) update_dep(k, 1, n, par[posy]);
}
int main() {
scanf("%d%d", &n, &m);
build(root[0], 1, n);
for (int i = 1, op, k, a, b; i <= m; i++) {
scanf("%d", &op);
if (op == 2) {
scanf("%d", &k);
root[i] = root[k];
} else {
scanf("%d%d", &a, &b);
if (op == 1) {
root[i] = root[i - 1];
merge(root[i - 1], root[i], a, b);
} else {
root[i] = root[i - 1];
if (par[find(root[i], a)] == par[find(root[i], b)])
puts("1");
else
puts("0");
}
}
}
}
1 条评论