概述
并查集主要是解决以下几种问题的：
- 各节点之间的关系
- 某节点和它祖先之间的关系
种类
- 朴素并查集，一个集合的信息可以存储在它的祖先节点上。
- 带权并查集，维护的是某节点与它祖先的关系。
- 扩展域并查集（种类并查集），本质是多开几倍空间的朴素并查集，维护的是各个阵营之间的关系，且几个域里具有对称性。形式化而言，可以把每个域看作一个平行时空，当朋友域里的我和朋友域里的他是朋友时，我和他是朋友；当朋友域里的我和敌人域里的他是朋友时，我和他是敌人。
模板
朴素并查集模板
点击查看代码
int findf(int x)
{
if(f[x]!=x)f[x]=findf(f[x]);
return f[x];
}
带权并查集模板
点击查看代码
int findf(int x)
{
if(f[x]==x)return x;
int orif=f[x];
f[x]=findf(f[x]);
dis[x]+=dis[orif];
return f[x];
}
种类并查集模板
朴素并查集上多开几倍空间。
求最大连通块点数
朴素并查集，把该连通块信息算在祖先节点上，combine 时就传递祖先节点的信息。
求连通块数量
祖先节点的个数就是连通块数量，因此遍历每一个点，如果 findf(i)==i 则 num++ 。
套路
- 几个点之间可以任意交换，则他们是一个集合，常用于序列上的并查集问题。交换
- 带权并查集的权值取模，可以当成种类并查集来用。食物链
- 建立虚点，来实现两个集合合并时，不影响两个集合原来各自的操作，且后续共享操作的功能。网络分析
- 破坏两个节点间的关系，反向合并集合，从最后一次破坏开始，往前合并破坏的节点。星球大战
- 判断两种说法是否矛盾，把相同的说法加入同一个并查集里；可以在一开始时就判断矛盾，也可以在最后才判断。程序自动分析
- 判断图的连通性，如 Kruskal 算法。
- 最少的任意位置的交换次数，把要交换的东西合并成一个集合，交换次数即为 \(size-1\) 。情侣牵手
- 判断是否有环的存在。
- 超级源点，这个超级源点既可以看作是把整个集合赋某个特定的值，也可以看作是给一些满足要求的节点连边。三值逻辑，被围绕的区域