修复公路

采用并查集维护村庄的连通关系，按公路修复时间升序处理，每次合并公路连接的村庄，直到所有村庄连通，此时的时间即为最早连通时间

#include<bits/stdc++.h>
using namespace std;

int fa[10000]; 
int n,m;   
// 存储公路信息
struct node
{int x,y,t;
}a[1000000];
bool cmp(node fir,node sec)
{
	return fir.t<sec.t;
}
int gf(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=gf(fa[x]);
}
void ad(int x,int y)
{
	int fx=gf(x); // 找x的根节点
	int fy=gf(y); // 找y的根节点
	fa[fx]=fy;    // 合并两个连通集
}

// 检查是否所有村庄连通
bool check()
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i) sum++; // 统计根节点数量
		if(sum==2) return 0; 
	}
	return 1; // 只有一个根节点，全连通
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	// 初始化
	for(int i=1;i<=n;i++) fa[i]=i;
	// 读入所有公路信息
	for(int i=1;i<=m;i++) cin >> a[i].x >> a[i].y >> a[i].t;
	sort(a+1,a+m+1,cmp);
	
	// 依次处理每条公路
	for(int i=1;i<=m;i++)
	{
		ad(a[i].x,a[i].y); // 合并当前公路连接的两个村庄
		if(check())        // 所有村庄已连通
		{
			cout << a[i].t << endl; // 输出当前公路的修复时间
			return 0;
		}
	}
	// 所有公路处理完仍未全连通
	cout << "-1" << endl;
	return 0;
}