0%

并查集及应用

并查集

首先,关于并查集的介绍可以查看这篇有趣的博客

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int pre[1000];  //pre[i]记录的是节点i的前导节点(parent)

int find(int x){ //find函数用于寻找x的最上级(root)

while(pre[x]!=x){ //当自己不是root时,通过自己的parent寻找自己的root
x=pre[x];
}

return x;
}

int join(int x,int y){ //将x和y合并到同一个集合

int fx=find(x),fy=find(y);

if(fx!=fy){ //如果x和y的root不同,则将fx的parent指向y
pre[fx]=fy;
}

}

优化

以上讲清了并查集的思想,但查找的树状结构也许会过深,导致查找效率低下。于是引入了路径压缩的概念:

路径压缩:为了优化查找树的结构,查找时将x到root节点路径上的所有点的parent设为root。

find函数代码优化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 ];
pre[ i ]= r ;
i=j;
}
return r ;

再次优化

为了代码的简洁与优雅,find函数其实可以再次进行优化:

1
2
3
4
5
6
int find(int x){
if(pre[x]!=x){
pre[x]=find(pre[x]);
}
return pre[x];
}

连通分量

题目来源于牛客网:

https://www.nowcoder.com/practice/7c29cdfa28274c86afc9e88c07448a10?tpId=40&tPage=1&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking&tab=answerKey

思路如下:

  1. 将pre数组初始化,每个x的parent都是-1.
  2. 读取输入的(x,y),将x,y合并
  3. 遍历pre数组,如果x的root是自身,则连通分量+1.
-------------------本文结束 感谢阅读-------------------