1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m表示边数 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值 5 bool cmp(edge a,edge b) 6 { 7 return a.w<b.w; 8 } 9 int fa[maxn];//因为需要用到并查集来判断两个顶点是否属于同一个连通块 10 int find(int x) 11 { 12 if(x==fa[x]) return x; 13 else return fa[x]=find(fa[x]); 14 } 15 int kruscal() 16 { 17 int ans=-1; 18 sort(e+1,e+1+m,cmp); 19 for(int i=1;i<=n;++i) fa[i]=i;//初始化并查集 20 int cnt=n; 21 for(int i=1;i<=m;++i) 22 { 23 int t1=find(e[i].u); 24 int t2=find(e[i].v); 25 if(t1!=t2) 26 { 27 if(cnt==1) break; 28 fa[t1]=t2; 29 ans=max(ans,e[i].w); 30 cnt--; 31 } 32 } 33 return ans; 34 }