백준 1197 - 최소 스패닝 트리 (Cpp)

링크

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

전체 소스 코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define endl '\n';
using namespace std;

int find(int node, vector<int>& v) {
    if (node == v[node]) {
        return node;
    }
    return v[node] = find(v[node], v);
}

void merge(int a, int b, vector<int>& v) {
    if (a != b) {
        v[a] = b;
    }
}

int main(void) {
    int vertex, edge;
    int totalWeight = 0;
    cin >> vertex >> edge;

    vector<pair<int, pair<int, int>>> edges = vector<pair<int, pair<int, int>>>(vertex + 1);
    vector<int> v = vector<int>(vertex + 1);

    for (int i = 0; i < v.size(); i++) {
        v[i] = i;
    }

    for (int i = 0; i < edge; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;
        edges.push_back({weight, {from, to}});
    }

    sort(edges.begin(), edges.end());

    for (auto we : edges) {
        int weight = we.first;
        pair<int, int> e = we.second;
        int from = e.first;
        int to = e.second;

        int setA = find(from, v);
        int setB = find(to, v);

        if (setA != setB) {
            totalWeight += weight;
            merge(setA, setB, v);
        }
    }

    cout << totalWeight << endl;

    return 0;
}