BOJ 1197 최소 스패닝 트리

1 개요

BOJ 1197 최소 스패닝 트리

• 백준 온라인 저지 1197번 문제
• BOJ 37단계

2 C++

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

int V, E;
int parent[10001];
vector<pair<int, pair<int, int>>> v;

int Find(int x) {
    if(parent[x] == x) return x;
    return Find(parent[x]);
}

void Union(int x, int y) {
    parent[Find(y)] = Find(x);
}

void solve() {
    sort(v.begin(), v.end());
    int sum = 0;
    for(int i=0; i<E; i++) {
        int k = v[i].first;
        int m = v[i].second.first;
        int n = v[i].second.second;
        if(Find(m) == Find(n)) {
            continue;
        }
        Union(m, n);
        sum += k;
    }
    cout << sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E;
    for(int i=0; i<=V; i++) {
        parent[i] = i;
    }
    int A, B, C;
    for(int i=0; i<E; i++) {
        cin >> A >> B >> C;
        v.push_back({C, {A, B}});
    }
    solve();
}