1939번: 중량제한

https://www.acmicpc.net/problem/1939


$O(n+m\lg m)$

큰 가중치의 간선부터 보면서 연결된 지점들을 합집합 시킨다.
처음으로 시작 지점과 도착 지점이 같은 집합에 있게 될 때 보았던 간선의 가중치가 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
struct st {
    int x, y, z;
    bool operator<(st i) const {
        return z>i.z;
    }
}e[100000];
int n, m, p[10001], s, d;
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i<m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    scanf("%d%d", &s, &d);
    sort(e, e + m);
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 0; i<m; i++) {
        p[f(e[i].x)] = f(e[i].y);
        if (f(s) == f(d)) { printf("%d", e[i].z); break; }
    }
    return 0;
}