GF2026提高组-并查集

• 导航页

• GF2026C1图的定义、存储和遍历

……

前言

并查集是一种用于管理元素所属集合的数据结构．

说句大实话，并查集学到$A2$的人都能实现代码部分($A2$都会)

并查集实现查找根节点的代码如下(手打函数):

int find(int x){
    return a[x]==x ? x : find(a[x]);
}

并查集路径压缩(不加概率TE):

int find(int x){
    return a[x]==x ? x : a[x]=find(a[x]);
}

并查集实现合并集合的代码如下:

int unite(int x,int y) { a[find(x)] = find(y); }

最小生成树代码模板(参考$luoguP3366$)

//典型并查集操作
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int MAXN=5005,MAXM=2e5+5;
struct add{
    int u,v,w;
}g[MAXM];
int a[MAXN],sum,cnt;
bool cmp(add a,add b){ return a.w<b.w;}
int find(int x){
    return a[x]==x ? x:a[x]=find(a[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=i;
    for(int i=1;i<=m;i++) cin>>g[i].u>>g[i].v>>g[i].w;
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;i++){
        int e1=g[i].u,e2=g[i].v;
        int b=find(e1),c=find(e2);//father
        if(cnt==n-1) break;//优化
        if(b==c) continue;//环
        cnt++;
        sum+=g[i].w;//长度和
        a[b]=c;
        
    }
    if(cnt!=n-1) cout<<"orz";
    else cout<<sum;
    return 0;
}