1197번: 최소 스패닝 트리

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


$O(e\lg v)$

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