백준 1197 최소 스패닝 트리 (C++)

1197번: 최소 스패닝 트리
크루스칼 알고리즘을 응용한 문제이다. 먼저 주어진 간선들을 오름차순으로 정렬을 해주고 가중치가 작은 간선부터 이어주기를 시작한다. 간선을 이어주던 중 만약 부모 노드가 같은 노드끼리 이어지게 되면 사이클이 발생하므로 부모 노드가 같은지 확인을 해준다. 이어준 후에 부모 노드를 합쳐주고 가중치를 더해주면서 반복문을 진행한다. 초기 parent배열은 자기자신을 부모 노드로 가지고 있도록 해준다.
어려웟던 문제였다. 크루스칼 알고리즘은 자주 사용될 것 같으니 알아둬야겠다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int findParent(int a) {
    if (parent[a] == a) return a;
    else return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a != b) parent[b] = a;
}

bool sameParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) return true;
    else return false;
}

void solution() {
    sort(v.begin(), v.end());

    for (int i = 1; i <= V; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < E; i++) {
        if (!sameParent(v[i].second.first, v[i].second.second)) {
            unionParent(v[i].second.first, v[i].second.second);
            res += v[i].first;
        }
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({ c,{a,b} });
    }

    solution();

    return 0;
}