RenaMoe's Blog

念念不忘，必有回响

0%

总结 并查集

发表于 更新于 分类于 ， Valine：

并查集用于处理一些不交集的 合并 及 查询 问题。

简易版

注意提前把father赋为自己！！！

1
2
for (int i = 1; i <= n; ++i)
    fa[i] = i;

含路径压缩的查找函数

1
2
3
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

合并函数

1
2
3
4
inline void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
}

路径压缩× 按秩合并√

某些题无法使用路径压缩，那就维护点数或者深度，按秩合并。

每次查询复杂度 \(O(logn)\)，不会证。

1
2
3
4
5
6
7
inline void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
    	if (size[x] > size[y]) swap(x, y);
        fa[x] = y, size[y] += size[x];
    }
}

带权并查集

当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系。

每个节点维护某种权值，在查找时合并根到其路径上的权值。

例题：P2024 [NOI2001]食物链

权值实际上是建立在边上的，我们可以用 0,1,2 分别代表同类、天敌和猎物。

查找时在模3意义下累加节点祖先的权值，可以推出节点和根和关系。

权值相减可以得到两个节点的关系。

扩展域并查集

将每个点拆成多个点来维护多组关系，种类并查集似乎属于扩展域并查集。

例题：P1525 关押罪犯

将每个点拆成罪犯的朋友和罪犯的敌人，分别形成集合，就可以判断矛盾关系了。

食物链也可以用扩展域并查集做，需要维护三个种类。