并查集
用来“快速将两个集合合并”、“询问两个元素是否在同一个集合中”的一种数据结构。
-
它依托于树形结构,树上每一个点所在集合与根节点所在集合一致,因此如果需要查询某个元素是否位于某个集合,一定要向上追溯到根节点再查看。
-
构建的具体操作是将,每一个节点,我们都存储一下它的父节点p[x]是谁。向上追溯,如果追溯到x==p[x]也就是父节点的父节点还是自己,那么说明来到根节点了,根节点的p[x]就是这棵树的集合编号。
问题1.如何将判断树根?if(p[x]==x)
只有根节点的编号是自己,其他的节点都是存的父节点编号
问题2.如何求x的集合编号?while(p[x]!=x) x=p[x]
x作为滑动指针向上追溯
问题3.如何合并两个集合?p[x]=y
把其中一棵树插到另外一颗树上,一般将其插入到根节点上就行
问题4.判断两个元素是否在同一个集合中?if(find(x)==find(y))
并查集的路径压缩:
基于问题2,每次查询祖宗节点都需要遍历一下自己所在的这棵树,每次遍历次数为树的高度,时间复杂度很难达到O(1)级别,但通过路径压缩之后,可以极大加速这个过程,使得查询能近乎达到O(1)级别。
//返回x的祖宗节点 + 路径压缩
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
简述一下整个过程,其实就是不断通过find(p[x])递归,直到找到符合该条件if(p[x]!=x)的祖宗节点,然后返回该祖宗节点的编号。最后p[x]=find(p[x]);为递归的精妙所在了,先是顺流而上一路查询到祖宗节点,最后退回到上层节点时把下面节点的p[x],也就是父节点都改成了根节点,return p[x];其实一直返回的都是根节点(或者说根节点的编号,因为对于根节点来说二者是一致的)。
并查集的初始化:
for(int i=1;i<=n;i++) p[i]=i;
//根节点的定义就是x==p[x]自己等于自己的编号,开始时每个节点都是一颗独立的树,只有自己一个节点,同时也是根节点
维护整个集合“节点个数”的并查集:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
//一定要先维护size,再合并并查集,否则find(b)和find(a)找的是同一个节点,没有意义了
当然,使用时不用过多的思考原理,只要记住
find(x)
的含义,就是返回x的祖宗节点。想太多容易钻牛角尖
维护”到祖宗节点距离“的并查集:
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];//路径压缩的同时累计到祖宗节点的距离
p[x] = u;
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量