并查集

2023-12-24 08:08:04

并查集

基本介绍

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

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

基本操作

（1）Union(Root1, Root2):把子集合Root2并入集合Root1中。要求这两个集合互不相交，否则不执行合并。
（2）Find(x)：搜索单元素x所在的集合，并返回该集合的名字。
（3）UnionFindSets(s):构造函数，将并查集中s个元素初始化为s个只有一个单元素的子集合。

引例（luogu P1551）

【题目背景】

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

【题目描述】

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

【输入格式】

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

【输出格式】

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

【输入样例】

【输出样例】

Yes
Yes
No

【算法分析】

不相交集合的合并及查询问题，可以使用并查集简单地进行如下做法：

（1）初始状态：

①合并1和2

②合并1和3

③合并5和4

④合并3和5

用fa[i]表示元素i的父亲节点，进行不断并到不同的集合中。

(2)代码实现

1 int  find(int x){//用非递归的实现
2     while(fa[x]!=x)x=fa[x];
3     return x;
4 }

1 int find(int x){//用递归的实现
2     if(fa[x]!=x)return find(fa[x]);
3     else return x;
4 }

(3)优化方法

以上做法当数据特殊时会出现超时

下面有一种优化的方法：

并查集的路径压缩

每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快。

第一步，找到根结点。第二步，修改查找路径上的所有节点，将它们都指向根结点。也就是说，“合并5和3”的时候，直接指向根节点1。

代码实现

1 int find(xint x){//寻找根节点编号并压缩路径
2     if(fa[x]!=x)fa[x]=find(fa[x]);
3     return fa[x];
4 }

1 void unionn(int x,int y){//合并两个集合
2     x=find(x);y=find(y);
3     fa[y]=x;
4 }

完整代码

#include<bits/stdc++.h>//万能头
using namespace std;
int f[10000];//father存父亲根
int find(int);
int main(){
    int n,m,k,x,y;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        f[i]=i;//开始自己是自己的祖先
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        int xf,yf;
        xf=find(x);
        yf=find(y);
        if(xf!=yf)
            f[xf]=yf;
    }
    for(int i=1;i<=k;i++){
        cin>>x>>y;
        int xf,yf;
        xf=find(x);//找祖先啦
        yf=find(y);
        if(xf==yf)cout<<"Yes"<<endl;//找到同样的祖先那肯定是亲戚啦
        else cout<<"No"<<endl;//不然就不是
    }
    return 0;
}
int find(int x){//直到找到集合代表，也就是自己是自己的祖先
    if(x==f[x])
        return x;//找到啦
    return f[x]=find(f[x]);//重点改进，压缩路径，可以省时间，虽然不加也不会超时
}

【总结】

以上就是并查集的基本介绍。

码农公寓

并查集