并查集 学习笔记

发表于 | 分类于 | | + s

模板及讲解

一份资料

拆点

把一个点拆成两个点比较简单不多说
例题: NOIP2010 T3

带权

例题: NOIP2010 T3
并查集维护一个$r$数组，表示$i->father(i)$的权值。
定理：一个并查集中从一个点出发，沿着它所指向的边一直走，并累加下路上的权值(如果边是反的那么就取权值的负数)，走一圈回来，累加的和模 最大值$+1$ 结果一定是$0$
路径压缩：
Markdown
由图，根据敌人的敌人是朋友(多于两个阵营不适合带权并查集)，新的$r_x$的值就是$(r_x+r_{f_r})\%(MaxWeight+1)$

合并的情况：$father(y)=x$，$x$是$a$的根，$y$是$b$的根
Markdown

由图，$(k+r_b+r_y-r_a)\%(MaxWeight+1)=0$，因为$y$合并至$x$，所以$r_y$变了，那么我们就算出$r_y$即可，$r_y=(-k-r_b+r_a+MaxWeight+1)\%(MaxWeight+1)$，其中加上$MaxWeight+1$是为了防止负数。
查询的情况(在一个集合)
Markdown

由图，如果$(k+r_b-r_a+MaxWeight+1)\%(MaxWeight+1)=0$的话，那么$a->b$就是$k$，我们就可以这样判断关系。

可撤销并查集

可以回退的并查集，复杂度大约$(logn)$
不能路径压缩，所以只能按秩合并 (启发式合并，siz小的合并到大的)
每次合并记录合并的两个点放到栈中，然后撤销时用栈顶来依次撤销

按秩合并:

void mg(int a, int b) {
    int x = a, y = b;
    if (sz[x] > sz[y]) swap(x, y);
    f[x] = y, sz[y] += sz[x], s.push(mp(x, y));
}

撤销操作：

void cc(int tms) {
    while (tms-- && !s.empty()) {
        pair<int, int > p = s.top(); s.pop();
        int x = p.fir, y = p.sec;
        f[x] = x, sz[y] -= sz[x];
    }
}

维护信息

一般可以维护$size$等信息。
例题：Luogu 1196
本题需要维护$d_i$表示$i$到根有多少个战舰和$size$。
查询输出$abs(d_x - d_y)-1$即可。

维护只删除链表 ( 跳过序列某一个值 )

通过让$x$成为$x-1$的儿子来删掉$x$位置，查询时$x$的根为他左边的第一个位置。
例题：Poj 1456
通过让$x$成为$x+1$的儿子来删掉$x$位置，查询时$x$的根为他右边的第一个位置。
例题：Bzoj 2054

维护数组(维护差分约束)

在$find$时，先递归$t=find(f(x))$，然后维护值，然后再使$f(x)=t$
差分约束：用并查集维护$c_i=s_i-s_{rt}$
例题: BZOJ 1202

网格图维护行列

在维护行列的并查集中，如果$r_i$与$c_i$连通则网格这个点被染色，整个图是连通的网格则所有点都被染色。
例题: Codeforces 1013D

相关代码

------ 本文结束 ------