并查集-蒲公英云

并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并
基本模板
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m;
int f[maxn];// 当前节点的父节点
int find(int x){ //路径压缩的写法 ，返回的该节点的祖宗节点
    if(x!=f[x]){ //如果一个点的父亲节点是本身就说明 
        f[x]=find(f[x]);
    }
    //查找x所在集合的祖先节点下标，将x的父亲节点指向祖先节点 
    return f[x];
}
int main(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++){ 
        f[i]=i;//首先将每个节点的父亲初始化为自己本身，自己是一个集合 
    }
    char c;
    while(m--){ 
        cin>>c;
        int a,b;
        if(c=='M'){ 
           cin>>a>>b;
           int fa=find(a);
           int fb=find(b);
           if(fa!=fb){ //如果a和b不是同一个集合 
                 f[fa]=fb;//将a的祖先节点的父亲指向b的祖先节点 
           }
        }
        else if(c=='Q'){ 
           cin>>a>>b;
          int fa=find(a);
           int fb=find(b);
           if(fa==fb){ //如果祖先节点相同说明在一个集合中 
               cout<<"Yes"<<endl;
           }
           else{ 
               cout<<"No"<<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≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int maxn=1e5+10;
int n,m;
int f[maxn];// 当前节点的父节点
int cnt[maxn];//统计集合内元素的数量
int find(int x){ //路径压缩的写法 
    if(x!=f[x]){ //如果一个点的父亲节点是本身就说明 
        f[x]=find(f[x]);
    }
    //查找x所在集合的祖先节点下标，将x的父亲节点指向祖先节点 
    return f[x];
}
int main(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++){ 
        f[i]=i;
        cnt[i]=1;//首先将每个节点的父亲初始化为自己本身，自己是一个集合 
    }
    string op;
    while(m--){ 
        cin>>op;
        int a,b;
        if(op=="C"){ 
           cin>>a>>b;
           int fa=find(a);
           int fb=find(b);
           if(fa!=fb){ //如果a和b不是同一个集合 
               cnt[fb]+=cnt[fa];
                 f[fa]=fb;//将a的祖先节点的父亲指向b的祖先节点 
           }
        }
        else if(op=="Q1"){ 
           cin>>a>>b;
          int fa=find(a);
           int fb=find(b);
           if(fa==fb){ //如果祖先节点相同说明在一个集合中 
               cout<<"Yes"<<endl;
           }
           else{ 
               cout<<"No"<<endl;
           }
        }
        else if(op=="Q2"){ 
            int a;
            cin>>a;
            cout<<cnt[find(a)]<<endl;
        }
    }
    return 0;
}