题解：P12222 [蓝桥杯 2023 国 Java B] 电动车

#include<bits/stdc++.h>
using namespace std;
struct dsu {
	vector<int>pa,size;
	int count;
	dsu(int n) {
		count = n;
		pa = size = vector<int>(n + 1, 1);
		iota(pa.begin(),pa.end(),0);
	}
	int find(int x) {
		return pa[x] == x ? x : pa[x] = find(pa[x]);
	}
	void merge(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return;
		if (size[x] < size[y]) swap(x, y);
		pa[y] = x;
		size[x] += size[y];
		count--;
	}
	bool pd(int x,int y) {
		return find(x) == find(y);
	}
};
struct edge{
	int u,v,w;
	bool operator < (const struct edge & rhs){
		return w<rhs.w;
	}
}e[200010];//按边排序
long long n,m,u,v,s,t,mi=INT_MAX;
vector<long long> g[200010];
long long node[200010],vis[200010];
int main(){
    cin>>n>>m;
    struct dsu uf(n);
    for(int i=1;i<=m;i++){
    	cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++){
		if(uf.pd(e[i].u,e[i].v)){
			continue;//已经连通就放弃
		}else{
            uf.merge(e[i].u,e[i].v);
        }
        if(uf.count==1){
            cout<<e[i].w<<endl;//图已经联通，这是最后且最大的一条边
            return 0;
        }
	}
	cout<<"-1"<<endl;//没结束说明不联通
	return 0;
}