백준 1197번 C++

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int parent[10001];

// 부모 노드 찾기
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

// 두 집합을 합치기
void uni(int x, int y) {
    x = find(x);
    y = find(y);
    parent[y] = x;
}

// 두 노드가 같은 집합에 속해 있는지 확인
bool sameparent(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return true;
    else return false;
}

int main() {
    int vertex, e;
    cin >> vertex >> e;
    int result = 0;
    vector<pair<int, pair<int, int>>> v;

    // 간선 정보 입력
    for (int i = 0; i < e; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        v.push_back({cost, {from, to}});
    }

    // 비용 기준으로 정렬
    sort(v.begin(), v.end());

    // 초기화: 각 정점이 자기 자신을 가리키도록
    for (int i = 1; i <= vertex; i++) parent[i] = i;

    // Kruskal 알고리즘 수행
    for (int i = 0; i < v.size(); i++) {
    	// i번째 간선의 시작 노드와 끝 노드가 같은 부모를 갖지 않으면
        if (!sameparent(v[i].second.first, v[i].second.second)) {
        	// 두 집합을 합치고
            uni(v[i].second.first, v[i].second.second);
            // 간선의 가중치를 비용에 더함
            result += v[i].first;
        }
    }

    // 최소 신장 트리의 총 비용 출력
    cout << result;

    return 0;
}