最小生成树

Kruskal 算法 O(mlogm)

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=2e5+10,INF=0x3f3f3f3f;


int n,m,dis[N],f[N];

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

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

int Kruskal()
{
  sort(edges,edges+m);

  for(int i=1;i<=n;i++) f[i]=i;//并查集初始化

  int res=0,cnt=0;

  for(int i=0;i<m;i++)
  {
    int a=edges[i].a,b=edges[i].b,w=edges[i].w;
    int f1=find(a),int f2=find(b);
    if(f1!=f2)
    {
      f[f1]=f2;
      res+=w;
      cnt++;
    }
  }

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


int main()
{
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    edges[i]={a,b,c};
  }

  int ans=Kruskal();
  if(ans==INF) puts("impossible");
  else printf("%d\n",ans);

  return 0;
}