【OI之路】03图论算法-4并查集Union-find Sets

3.3.1定义

并查集,顾名思义就是有“合并集合”和“查找集合”两种操作的关于数据结构的一种算法。

用途
1、维护无向图的连通性。支持判断两个点是否在同一连通块内,和判断增加一条边是否会产生环。
2、用在求解最小生成树的Kruskal算法里。

初始化
自己是自己的老大

3.3.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
找老大:
int findfa(int x)0
{
if(fa[x]==x) return x;
return fa[x]=findfa(fa[x]);
}
合并:
void join(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx!=fy) fa[fx]=fy;
}
检测环:
for(int i=1;i<=边数;i++)
{
int q=findfa(b[i].x);
int w=findfa(b[i].y);
if(q==w) return 1;//如果在一个集合,就找到了环
join(q,w);
}

3.3.3 进阶练习

魏总数星星
星球大战

3.3.4 所有题目

Tag-并查集

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/a89d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%