题解 | 修复公路

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e5+10;

int n,m; 
int fa[N];

struct Node{
	int x,y,t;
}a[M];

void pre(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	return;
}

bool cmp(Node u,Node v){
	return u.t<v.t;
}

int find(int x){
	if(fa[x]==x) return x;
	else{
		return fa[x]=find(fa[x]);
	}
}

void add(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx==fy) return;
	else{
		fa[fx]=fy;
	}
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	pre();
	int x,y,t;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>t;
		a[i].x=x;
		a[i].y=y;
		a[i].t=t;	
	}
	sort(a+1,a+1+m,cmp);
	
	int res=0;
	for(int i=1;i<=m;i++){
		if(find(a[i].x)!=find(a[i].y)){
			add(a[i].x,a[i].y);
			res=max(res,a[i].t);
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			cnt++;
		}
	}
	if(cnt==1){
		cout<<res<<endl;
	}else{
		cout<<-1<<endl;
	}
    return 0;
}