算法

(并查集+排序) $O(mlogm)$

先把所有边按修复时间从小到大排序，再每次取出权值最小的边，如果它的两个端点$u,v$已经联通了就跳过，否则就把这条边加入图中，并且把$u,v$加入到同一个集合中。 最后，如果取了$n-1$条边，则说明该图已联通，否则该图不能联通。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

int n, m; 
int p[1010];

struct Road {
    int u, v, t;
    bool operator < (const Road & f) const{
        return t < f.t;
    }
} r[100010];

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        cin >> r[i].u >> r[i].v >> r[i].t;
    }
    sort(r + 1, r + m + 1);

    for (int i = 1; i <= n; ++i) p[i] = i;

    int cnt = 0, ans = -1;
    for (int i = 1; i <= m; ++i) {
        if (find(r[i].u) == find(r[i].v)) continue;
        cnt++;
        p[find(r[i].u)] = find(r[i].v);
        ans = max(ans, r[i].t);
    }

    if (cnt == n - 1) cout << ans << '\n';
    else cout << -1 << '\n';

    return 0;
}