并查集

本文最后更新于 2020年4月7日 下午

并查集指的是一个图中的若干个连通分支，任意两个连通分支间没有关系，而每个连通分支内部可以以任意一个点作为根节点，根节点指向它自己，而其他点指向他们的上级节点（因为是连通图，两点之间必定可达），因此只要在同一连通分支，必定可以到同一根节点，从而判断两者可达

例如：pre[2]=3表示2的上级节点为3，pre[3]=3表示这是一个根节点

1
2
3
4
5
6
7
8

int find(int x)                    //查找我（x）的掌门
{
    int r=x;                      //委托 r 去找掌门
    while (pre[r ]!=r)           //如果r的上级不是r自己（也就是说找到的大侠他不是掌门 = =）
    r=pre[r ] ;                 // r 就接着找他的上级，直到找到掌门为止。
    return  r ;                //掌门驾到~~~
}

另外如何将两个连通分支合并为一个连通分支呢？

我们可以把任意一个根节点指向另外一个根节点（因为我们不考虑内部的关系，指向知道是否可达），这样就变为一个连通分支了

1
2
3
4
5
6
void join(int x,int y)          //我想让虚竹和周芷若做朋友
{
    int fx=find(x),fy=find(y);         //虚竹的老大是玄慈，芷若MM的老大是灭绝
    if(fx!=fy)                         //玄慈和灭绝显然不是同一个人
    pre[fx ]=fy;                       //方丈只好委委屈屈地当了师太的手下啦
}

路径压缩

如果我们要经转很多个上级才能找到根节点，这样显然效率较低，假如我们可以直接让自己的上级是根节点，那就再好不过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int pre[1000 ];
int find(int x)                                       //查找根节点
{ 
    int r=x;
    while ( pre[r] != r )                           //返回根节点 r
          r=pre[r];
 
    int i=x , j ;
    while( i != r )                                   //路径压缩
    {
         j = pre[ i ]; 				// 在改变上级之前用临时变量  j 记录下他的值 
         pre[ i ]= r ; 				//把上级改为根节点
         i=j;
    }
    return r ;
}

带权并查集

带权值的并查集只不过是在并查集中加入了一个value[ ]数组
value[ ]可以记录很多种东西，不一定是类似距离这种东西，也可以是相对于根节点的状态

1
2
3
4
5
6
7
8
9
int findfat(int x)
{
	if(fat[x] == x) return x;
	int tmp=fat[x];
	fat[x]=findfat(fat[x]);
	//在此处修改val比如：
	value[x]=value[tmp]+1;
	return fat[x]; 
}

参考文章

并查集
https://www.xinhecuican.tech/post/61809.html
作者
John Doe
发布于
2020年2月4日
许可协议