【算法与数据结构】并查集

并查集

合并和查询集合的数据结构，经常用于连通图，最小生成树$Kruskal$算法，最近公共祖先($LCA$​​)

查询的时间复杂度：小于O($lo{g}_{2}n$)近乎O(1)

【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例 #1

样例输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

样例输出 #1

N
Y
N
Y

提示

对于 $30\%$ 的数据，$N\le 10$，$M\le 20$。

对于 $70\%$ 的数据，$N\le 100$，$M\le 10^3$。

对于 $100\%$ 的数据，$1\le N\le 10^4$，$1\le M\le 2\times 10^5$，$1\le X_i,Y_i\le N$， Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi​∈{1,2}​。

p[x]=a代表x的父节点指向a

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int p[N];
int find(int x)//压缩路径+返回祖宗结点
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m,z,x,y;
    cin>>n>>m;
    for(int i=0;i<n;i++)p[i]=i;
    while(m--)
    {
        cin>>z>>x>>y;
        if(z==1)p[find(x)]=find(y);//合并集合,x的祖宗结点的父节点是y的祖宗结点
        else 
        {
            if(find(x)==find(y))cout<<"Y"<<endl;//两个元素有相同的祖宗结点说明他们在同一个集合
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤$10^5$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int p[N],size1[N];//用size1记录祖宗结点所在的集合中元素的数量
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m,a,b;char op[3];
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i]=i;size1[i]=1;//初始化并查集，认为每个i属于一个集合，他们自己就是该集合的祖宗结点，元素个数为1
    }
    while(m--)
    {
        cin>>op;
        if(op[0]=='C'){
            cin>>a>>b;
            if(find(a)==find(b))continue;//如果a,b来源于同一个集合，则不能合并，合并是关于不同集合的合并
            size1[find(b)]+=size1[find(a)];//这里的位置不能随意变动，否则合并后的size是新合并集合的2倍,还有这里的size1查询的是这个集合中的个数，要找到根节点才能查询个数，size1[b]是错的，一定要写成size1[find(b)],即b所在集合的元素个数
            //因此要先记录合并后的size，再合并集合
            p[find(a)]=find(b);
            
        }
        else if(op[1]=='1')
        {   cin>>a>>b;
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }else 
        {   cin>>a;
            cout<<size1[find(a)]<<endl;
        }
    }
    return 0;
}

原文地址：https://blog.csdn.net/2301_79728896/article/details/140635841

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！