洛谷P1111 修复公路

url: https://www.luogu.com.cn/problem/P1111

tag:
kruskal算法, 并查集

思路：
先按照边权排序，然后依次取出每条边，判断两个点是否联通（是否在一个集合）如果不连通就加一条边，然后更新下res = max(res, w) 然后边数++，最后判断边数是否为点个数-1，表示所有点都连上，如果没有则输出-1，否则输出res

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
struct edg {
    int x, y, t;
} Edg[N];
bool cmp(edg &a, edg &b)
{
    return a.t < b.t;
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> Edg[i].x >> Edg[i].y >> Edg[i].t;
    }
    sort(Edg + 1, Edg + m + 1, cmp);
    for (int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        int a = find(Edg[i].x), b = find(Edg[i].y), w = Edg[i].t;
        if (a != b)
        {
            p[a] = b;
            res = max(res, w);
            cnt ++;
        }
    }
    if (cnt < n - 1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}