搜索与图论

kruscal算法

时间复杂度是 O(mlogm), n 表示点数，m 表示边数

#include<iostream>
using namespace std;

int n,m;// n是点数，m是边数
int p[N];// 并查集的父节点数组

struct Edge{// 存储边
    int a,b,w;
    bool operator<(const Edge &W)const{
        return w<W.w;
    }
}edges[M];

int find(int x){//并查集核心操作
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}

int kruscal(){
    sort(edges,edges+m);
    for(int i=1;i<=n;++i)p[i]=i;

    int res=0,cnt=0;//cnt记录连通的边数

    for(int i=0;i<m;++i){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;

        a=find(a),b=find(b);
        if(a!=b){ // 如果两个连通块不连通，则将这两个连通块合并
            p[a]=b;
            res+=w;
            cnt++;
        }
    }

    if(cnt<n-1)return INF;
    return res;
}