kruskal也不怕自环和重边

kruskal也不怕自环和重边
因其有并查集和排序的操作
排序保证了每次选最优边
并查集保证每次两点不在同一集合，所以保证了无重边和自环

此题分析：两点在同一集合表示已联通

#include<bits/stdc++.h>
using namespace std;
int const M=2e4+7;
int const N=1e4+7;
struct node{
  int a,next,len;
  friend bool operator<(node a,node b){
    return a.len < b.len ;
  }
}e[M];
int f[N];
int find(int x){
  return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
  f[find(x)]=find(y);
}
int n,m,s,t;
int kruskal(int mid){
  sort(e+1,e+n+1);
  for(int i=1;i<=n;++i) f[i]=i;
  for(int i=1;i<=m;++i){
    int a=e[i].a , b=e[i].next ;
    if(e[i].len <=mid &&find(a)!=find(b)){
      merge(a,b);
      if(find(s)==find(t)) return 1;
    }
  }
  return 0;
}
int main(){
  cin >> n >> m >> s >> t;
  for(int i=1;i<=m;++i){
    cin >> e[i].a >> e[i].next >> e[i].len ;
  }
  int l=0,r=2e4;
  while(l<=r){
    int mid=(l+r)>>1;
    if(kruskal(mid)) r=mid-1;
    else l=mid+1;
  }
  cout << l << endl;
  return 0;
}