并查集练手题
P1111修复公路

只能说是题解说的都不太清楚所以在这里Mark一下（
题目要点：所有公路是同时开始修复的，这是这道题最为基本的逻辑

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
    int x, y, t;
}a[100010];
bool flag=0;
bool cmp(node a, node b)
{
    return a.t < b.t;
}
int father[1001], n, m;//father数组Index表示当前节点，Value表示父节点
int searchFather(int x) {
    if (father[x] == x) {
        return x; //代表找到了祖先节点
    }
    return father[x] = searchFather(father[x]);//如果没有找到 继续找
}
void claimFather(int x, int y) {
    int tx = searchFather(x);//找到x，y两点的祖先节点
    int ty = searchFather(y);
    father[tx] = ty;//ty为tx父节点，即两个互相连接的祖先节点
    //即，题目给的N个祖先节点最终都会互相连接，而被链接的祖先节点将不再是祖先节点
    //只剩下一个祖先节点的时候，代表所有村庄都连接到了一起。
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        father[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++) {//从最短时间开始遍历，因为所有路是同时开始修复的；
        claimFather(a[i].x, a[i].y);
        int num = 0;
        for (int i = 1; i <= n; i++) {
            if (father[i] == i) {
                num++;
            }
            if (num >= 2) {//祖先节点在两个以上 跳过；
                break;
            }
        }
        if (num == 1) {//如果只有一个祖先节点 ，代表联通。
            cout << a[i].t;
            flag = 1;
            break;
        }
    }
    if (!flag) cout << "-1";
    return 0;
}