1922 네트워크 연결

MST 문제다. 크루스칼 알고리즘을 사용했다.

#include <stdio.h>
#pragma warning(disable:4996)
typedef long long ll;
int n, m;
 
struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};
 
edge arr[100001];
 
void _sort(int l, int r) {
    if (l == r || r - 1 == l) return;
    int mid = (l + r) / 2;
    _sort(l, mid);
    _sort(mid, r);
 
    edge *temp = new edge[r - l];
    int cur = 0, l_cur = l, r_cur = mid;
    while (l_cur < mid && r_cur < r) {
        if (arr[l_cur].w < arr[r_cur].w) {
            temp[cur++] = arr[l_cur++];
        }
        else
            temp[cur++] = arr[r_cur++];
    }
    for (; l_cur < mid; l_cur++) temp[cur++] = arr[l_cur];
    for (; r_cur < r; r_cur++) temp[cur++] = arr[r_cur];
    for (int i = 0; i < r - l; i++) arr[l + i] = temp[i];
}
 
int d[1001];
 
int f(int x) {
    return x == d[x] ? x : d[x] = f(d[x]);
}
 
void u(int x, int y){
    x = f(x);
    y = f(y);
    if (x != y) d[y] = x;
}
 
int main() {
    for (int i = 0; i < 1001; i++) d[i] = i;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        arr[i] = { a, b, c };
    }
    _sort(0, m);
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        if (f(arr[i].u) != f(arr[i].v)) {    
            u(arr[i].u, arr[i].v);
            ans += arr[i].w;
        }
    }
    printf("%lld", ans);
 
    return 0;
}