并查集 + krustal + P3367 + P1111题解

博主正在努力更新,该文章尚未完成!

并查集

什么是并查集?

Oi-wiki解释:

并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作:
·查找(Find):确定某个元素处于哪个子集;
·合并(Union):将两个子集合并成一个集合。
*也就是说,不支持集合的分离、删除。

百度百科解释:

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

我们来一道题目来看:

题面描述

规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
然后告诉你一些有亲戚关系的人,最后让你输出他们是不是亲戚。

那么这个就可以用到并查集算法。并查集算法的大致思路就是如果a和b是亲戚,那么就把b标注为a的编号。这时候,如果b和c是亲戚,那么就把c标注为b编号中的那个人,也就是把c标注为a。也就是找到亲戚的boss并如果是,就可以了。
unite是合并的意思,就是把他们两个亲戚标注为同一个类似于boss的东西

1
2
3
4
void unite(int x,int y) {
int xi=find(x),yi=find(y);
id[xi]=yi;
}

find就是找到他们的boss并返回。

1
2
3
4
int find(int x) {
if(id[x]==x) return x;
return id[x]=find(id[x]);
}

然后前m个就执行unite,后p个就之心find
最终代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int id[5020];
int find(int x) {
if(id[x]==x) return x;
return id[x]=find(id[x]);
}
void unite(int x,int y) {
int xi=find(x),yi=find(y);
id[xi]=yi;
}
int main() {
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(int i=0;i<n;i++)
id[i]=i;
for(int i=0;i<m;i++) {
int x,y;
scanf("%d%d",&x,&y);
unite(x,y);
}
for(int i=0;i<p;i++) {
int x,y;
scanf("%d%d",&x,&y);
if(find(x)==find(y)) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}

动态演示:https://visualgo.net/zh/ufds

推荐题目:

  1. 洛谷P3367 【模板】并查集
  2. 洛谷P1551 亲戚
  3. 洛谷P1111 修复公路(需要krustal)
支持原创!从我做起~ 支付宝搜“611460069”领到的红包也可以赞助哦~
召唤伊斯特瓦尔