并查集

带权并查集

带权指 子节点与父节点之间存在限制条件, 如子节点在父节点左边的x米处

接下来面临的两个难点:

  • 路径压缩时权值的变化
  • 两棵树合并时权值的变化
1
2
3
4
5
6
7
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];
}

删点

因为并查集是一个树形结构,所以你很难在很低的时间复杂度内,删除一个点,并且维护原来的关系不变。

这里我们对每个节点初始的时候连到一个相应的虚父节点,比如1节点就连到1+n节点。 这样每次合并都用其父节点进行合并。 删除某个节点的时候直接将该节点指向一个新节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

删边

将所有操作离线。

我们先把最后的状态建出来,然后逆着查询,这样原来的删边操作就变成了加边操作。