[백준 1922] 네트워크 연결, C++

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

1922번: 네트워크 연결

 본 문제는 최소 스패닝 트리를 구하는 문제다. 최소 스패닝 트리를 구하는 대표적인 방법으로는 prim, kruskal이 있다. 이번 문제는 kruskal을 이용하여 문제를 해결하였다. kruskal을 구현하기 위해선 우선 union-find 자료구조를 구현해야한다. 그리고 간선의 최소 비용을 먼저 연결하면 된다.

#include <cstdio>
#include <tuple>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int parent[10001];
int Rank[10001] = { 0 };
 
bool cmp(tuple<int, int, int> x, tuple<int, int, int> y) {
    int x1, x2, x3;
    int y1, y2, y3;
    tie(x1, x2, x3) = x;
    tie(y1, y2, y3) = y;
    return x3 < y3;
}
 
int Find(int x) {
    if (x == parent[x]) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (Rank[x] < Rank[y]) swap(x, y);
    parent[y] = x;
    if (Rank[x] == Rank[y]) Rank[x] += 1;
}
 
int main() {
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        v.push_back(make_tuple(x, y, z));
    }
    sort(v.begin(), v.end(), cmp);
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        tie(x, y, z) = v[i];
        x = Find(x);
        y = Find(y);
        if (x != y) {
            Union(x, y);
            ans += z;
        }
    }
    printf("%d\n", ans);
}