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 }