并查集 思路及模板代码及其变型

思路及模板代码及其变型"/>

并查集 思路及模板代码及其变型

数据结构介绍

并查集主要用于实现两个功能：

• 并：将两个集合合并
• 查：询问两个元素是否在一个集合当中

能够在近乎O(1)的时间复杂度内快速地维护

基本思想

每个集合用一棵树来表示，树的根节点下标是整个集合的编号，每个结点存储它的父节点，p[x]表示x的父节点

问题1：如何判断树根？

刚开始的时候，将p[x]数组初始化为数组元素＝下标
那么经过一通操作，可通过 ： if(p[x]==x) 来判断是否是树根
因为根节点的p[]值不用指向它的父亲，它没有父亲嘛

问题2：如何求x的集合编号？

while(p[x]!=x)x=p[x];

问题3：如何合并两个集合：p[x]是x的集合编号，p[y]是y的集合编号。

p[x]=y;

相当于把x集合的根节点作为y集合的根节点的一个子节点，从而代表x集合的树成了y集合的子树，y集合的根节点为x集合所有结点的根节点。

路径压缩优化

在集合合并或者在往集合里添加结点时，直接向根节点引一条边，使得集合中所有的结点都是根节点的直接子结点，集合代表的树的层数为2（根+所有子）。

核心代码

......
const int N = 100010;int p[N];int main()
{int n, m;scanf("%d%d", &n, &m);    //下标范围看具体题目而定for (int i = 1; i <= n; i ++ ) p[i] = i;   //初始化并查数组，每个结点都是独立的，都是自己单点集的父节点，所以这样初始化......
}

int find(int x)            //找结点x的父节点的同时作路径压缩（这里作了路径压缩，所以就是在找根节点）
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}

变体：需要记录每个集合中元素的个数（AcWing837）

find函数不变，给每个节点增加一个属性：size
用数组size表示
假定size属性只有对单个集合的根节点才是有意义的。
起初，所有点独自成一个集合，所以这时候size应该初始化为1，且是有意义的，在后续合并的过程中，有些非根节点的结点的size属性逐渐失去意义。

核心代码

if(op[0]=='C'){scanf("%d%d",&a,&b);a=find(a);   //先把合并前a，b所在集合的根节点序号定下来b=find(b);   //防止后面先进行 p[a]=b;赋值时，改变结果 s[b]+=s[a];的值if(a==b)continue;else{              //find(a)和find(b)的值先定为a,bp[a]=b;      //所以这两条语句的次序无关紧要s[b]+=s[a];   //前一句的执行不会影响到后一句}}

或者这么写：

if(op[0]=='C'){scanf("%d%d",&a,&b);if(find(a)==find(b))continue;else{s[find(b)]+=s[find(a)];   //得这一句在前p[find(a)]=find(b);       //如果后一句在前，执行完这句，后面find(a)的值和find(b)的值一样了，再执行s[find(b)]+=s[find(a)];就是错的答案了，相当于是把它×了2}}