并查集

• UnionFind

  一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题

  • 联通子图

  • 最小生成树Kruskal算法

  • 最近公共祖先LCA

• 不交集：没有重复元素的集合

• 合并Union：二变一

• 查询Find：确定元素所属集合，通常返回集合内的一个代表元素

实现思路

基于数组

#include<iostream>
using namespace std;
const int maxn=1050;
int s[maxn+1];

//initialize
void init_UF( ){
    for(int i=1;i<=maxn;i++)//id--集合编号
        s[i]=i;//set集合元素
}

int find_UF(int x){
    return x==s[x]?x:find_UF(s[x]);
    //找到则返回id（父节点）没找到就递归
}

void union_UF(int x,int y){
    int x_fa=find_UF(x);
    int y_fa=find_UF(y);
    if(x_fa!=y_fa)//不是同一个父节点
        s[x]=s[y];//y父给x，则同父
}

int main(){
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init_UF();
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            union_UF(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++){ //统计有多少个集
            if(s[i]=i)//代表元的个数
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

路径压缩--查询的优化

完全压缩

按秩合并--合并的优化