[BOJ] 백준 1197 최소 스패닝 트리

문제 링크

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

풀이

기본적인 유니온 파인드 문제입니다.

자세한 설명은 다른 블로그를 참고해주세요.

 

정답 코드

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

int n, m;
int par[11'111];

struct Edge {
    int u, v, c;

    Edge(int u = 0, int v = 0, int c = 0) : u(u), v(v), c(c) {}
};

vector<Edge> p;

int find(int x) {
    if (par[x] == -1) return x;
    return par[x] = find(par[x]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(par, -1, sizeof(par));
    cin >> n >> m;
    while (m--) {
        int u, v, c;
        cin >> u >> v >> c;
        p.emplace_back(u, v, c);
    }
    sort(all(p), [&](const auto &a, const auto &b) {
        return a.c < b.c;
    });
    int ans = 0;
    for (Edge &e: p) {
        auto[u, v, c] = e;
        u = find(u);
        v = find(v);
        if (u != v) {
            par[u] = v;
            ans += c;
        }
    }
    cout << ans;
}