최소 스패닝 트리

C++

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct Edge_t Edge;

struct Edge_t {
    int from, to, weight;
    bool operator < (const Edge a) const {
        return weight < a.weight;
    }
};

int r[10001];
int s[10001];

int Find(int i) {
    if (r[i] == i) return i;
    else {
        r[i] = Find(r[i]);
        return r[i];
    }
}

void Union(int i, int j) {
    int I = Find(i), J = Find(j);
    if (s[I] > s[J]) {
        r[J] = I;
    } else if (s[I] < s[J]) {
        r[I] = J;
    } else {
        r[J] = I;
        s[I]++;
    }
}

int main(int argc, const char * argv[]) {
    
    int V, E;
    scanf("%d%d", &V, &E);
    
    vector<Edge> e;
    for (int i = 0; i < E; i++) {
        int A, B, C;
        scanf("%d%d%d", &A, &B, &C);
        e.push_back({A, B, C});
    }
    
    for (int i = 1; i <= V; i++) {
        r[i] = i;
        s[i] = 1;
    }
    
    sort(e.begin(), e.end());
    
    int count = 0;
    int answer = 0;
    for (vector<Edge>::iterator it = e.begin(); it != e.end(); it++) {
        if (Find(it->from) != Find(it->to)) {
            Union(it->from, it->to);
            count++;
            answer += it->weight;
            if (count == V-1) break;
        }
    }

    printf("%d\n", answer);
    return 0;
}