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

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

MST를 구현해주면 되고, 크루스칼 알고리즘을 이용한다.

크루스칼 알고리즘은 유니온 파인드를 그대로 옮겨 놨다고 봐도 상관이 없다.

0. 유니온 파인드를 활용하기 때문에, 최상위 부모노드의 값을 자기 자신으로 초기화한다.

1. 간선 정보를 비용 오름차순으로 정렬한다.

2. 간선의 시작점과 끝점을 union해보면서, 같은 그룹에 속해있지 않다면, union 해주고 간선 비용을 추가해준다.

이미 같은 그룹이라면 연결되어 있다는 의미이기 때문에 비용에 더해주지 않고 스킵한다.

3. 모든 노드를 연결하는데에 필요한 간선의 개수는 n-1개이다. 따라서 n-1개 만들었으면 그만두고 반복문을 빠져나오자.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n, e, r[10002];
struct EDGE {
    int from, to, cost;
};
vector<EDGE> edge;
bool cmp(EDGE a, EDGE b) {
    return a.cost < b.cost;
}
int getParent(int a) {
    if (r[a] == a) return a;
    else return r[a] = getParent(r[a]);
}
bool join(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) return false; //이미 연결되어 있음
    else if (a < b)
        r[b] = a;
    else
        r[a] = b;
    return true;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> e;
 
    while (e--) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge.push_back({ src, dst, cost });
    }
    sort(edge.begin(), edge.end(), cmp);
 
    for (int i = 1; i <= n; i++)
        r[i] = i;
 
    //연결 안 되어 있는 노드 찾아서 연결 해보고, 연결 안 되어 있으면 연결하고 비용 추가
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < edge.size(); i++) {
        if (join(edge[i].from, edge[i].to)) {
            res += edge[i].cost;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    printf("%lld ", res);
 
    return 0;
}