数据结构之并查集数据结构之并查集

什么是并查集其他数据结构传送门
数据结构之堆
数据结构之栈
数据结构之队列
数据结构之并查集与二分图
并查集是个神奇的树型的数据结构，多用于查看几个元素是否有关系，一般并查集构造成下图:
文章图片
由此我们可以很容易地知道2和6是联通（有关系）的，因为他们他们的父亲都是1
并查集的用处在一些有N个元素的集合应用问题中，通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，所以只能用并查集来描述。如何构造和维护并查集以下图举例

文章图片

初始化把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

int fa[10010] for(int i=1; i<=n; i++){ fa[i]=i; }//相当于自己就是自己的根

于是乎

文章图片

查找查找元素所在的集合，即根节点。

int get(int x){//用dfs往上走即可 if(fa[x]==x){//已经找到根 return x; }else{ int y=get(fa[x]); //他父亲的根 fa[x]=y; //在中间边找边连可以节约很多时间，也保证构造后掉并查集深度一定为2层 return y; //返回他自己的根 } } fa[get(x)]=get(y); //连

最后通过fa就可以知道他的父亲是谁,再判断2个点的父亲是否相同即可知道是否有"关系"
把所有跟根相连的直接挂上去:
但之前所连的就会被下次覆盖掉
蓝色的表示所访问的过程,红色表示边

文章图片

合并将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
这样我们就可以用o(1)的时间复杂度去判断两个点是否在同一个集合(有关系)，对于一些层很深的图来说，这样无疑快了很多。
例题朋友在社交的过程中，通过朋友，也能认识新的朋友。在某个朋友关系图中，假定 A 和 B 是朋友，B 和 C 是朋友，那么 A 和 C 也会成为朋友。即，我们规定朋友的朋友也是朋友。
现在，已知若干对朋友关系，询问某两个人是不是朋友。
请编写一个程序来解决这个问题吧。
输入格式第一行：三个整数，分别表示有个人，个朋友关系，询问对朋友关系。
接下来行：每行两个数，，表示和具有朋友关系。
接下来行：每行两个数，询问两人是否为朋友。
输出格式输出共行，每行一个 “Yes” 或 “No” 。表示第个询问的答案为是否朋友。
样例输入 6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
样例输出 Yes Yes No
对于这道题来，只需要每次输入两个数就连边并维护并查集，最后看某两个数的根节点是否相同即可 【数据结构之并查集】代码：

#include using namespace std; int n,m,p; int fa[10010]; void init(){ for(int i=1; i<=n; i++){ fa[i]=i; } } int get(int x){ if(fa[x]==x){ return x; }else{ return get(fa[x]); } } int main(){ cin>>n>>m>>p; init(); for(int i=1; i<=m; i++){ int x,y; cin>>x>>y; fa[get(x)]=get(y); } for(int i=1; i<=p; i++){ int x,y; cin>>x>>y; if(get(x)==get(y)){ cout<<"Yes"; }else{ cout<<"No"; } cout<<" "; } return 0; }

下期——带权的并查集