并查集
并查集(Union-Find Set)
概念
并查集正如其名,分为Union和Find,即合并和查找。
代表元
我们用集合中某个元素来代表这个集合,称为代表元。
一个集合中的所有元素形成以代表元为根结点的树形结构。
对于每一个元素parent[x]指向x在树形结构中的父节点,如果x是根结点,则令parent[x]=x。
查找操作(Find)
就是依据parent[x]一路往上爬,最后找到代表元,从而确定自己所在的集合。
路径压缩(查找优化)
为了加快查找速度,我们把x到根结点上的路径上的所有结点的parent都设为根结点。
合并(Union)
连接两个非连通块,成为新的连通块,其中一个根结点成为新块的根结点。
基本操作
一般,并查集分三个操作
初始化
对所有单个数据建立一个单独的集合(即根据题目的意思自己建立的最多可能有的集合,为下面的合并查找操作提供操作对象)
一般来说,每一个单个的集合有三个要素:
- 集合所代表的数据(自定义)
- 集合的层次,用rank表示(初始化一般将rank都初始化为0)
- 集合的类别,用parent或是set表示(用指针指示)
有的题里面集合的数据就是这个集合的标号,也就是说只包含2和3,1省略了
初始化的时候,一个集合的parent都是这个集合自己的标号
。没有跟它同类的集合,那么这个集合的源头只能是自己了。
表示方法有两种,结构体和数组,题目简单用数组遍历,复杂则用结构体有条理些。
查找函数
查找就是要找到parent的源头,1
2
3
4
5
6
7int Find(int i)
{
if(fa[i]==i)
return i;
else
Find(fa[i]);
}
路径压缩:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int UniFind(int a)
{
int root=a;
while(root!=fa[a]) //Find the root
root=set[a];
while(a!=root) //compress the path
{
int parentof_a=fa[a]; //记录a的父结点
fa[a]=root; //令当前结点的父节点为root
a=parentof_a;
}
return root;
}
还有一种递归写法:1
2
3
4int UniFind(int a)
{
return fa[a]==a?a:(fa[a]=UniFind(fa[a]));
}
合并操作
最简单的合并只涉及代表元:1
2
3
4
5
6
7
8
9
10void Union(int i,int j)
{
int x=Find[i];
int y=Find[j];
if(x==y) return ;
else
fa(x)=y;//or fa[y]=x;
//没有考虑rank
}
若涉及rank,则如下:1
2
3
4
5
6
7
8
9
10
11
12
13void Union(int a,int b)
{
int x=Find[a];
int y=Find[b];
if(x==y) return;
if(rank[x]>rank[y])
fa[y]=x;
else
{
if(rank[x]==rank[y]) rank[y]++;//新结点的深度加1
fa[x]=y;
}
}
rank小的向rank大的靠拢,以至于树不会退化严重。
用途
- kruskal算法中增加一条边判断是否成环
- 维护连通性。判断两个点是否在同一个连通块中,例如有向图中判断其是否为有向树。