[백준] #1197 램프

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

1197번: 최소 스패닝 트리

---

1. 해결방법

크루스칼 알고리즘과 Union find를 이용하여 해결.

---

2. 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
vector<pair<int, pair<int, int>>> vec;
int Parent[10001];
int result = 0;

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) Parent[y] = x;
}

bool SameParent(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return true;
    return false;
}

int main(int c, char** v)
{
    cin >> N >> K;

    for (int i = 0; i < K; i++) {
        int x = 0, y = 0, cost = 0;
        cin >> x >> y >> cost;
        vec.push_back(make_pair(cost,make_pair(x, y)));
    }
    sort(vec.begin(), vec.end());
    for (int i = 1; i <= N; i++) {
        Parent[i] = i;
    }

    for (int i = 0; i < K; i++) {
        if (SameParent(vec[i].second.first, vec[i].second.second) == false) {
            Union(vec[i].second.first, vec[i].second.second);
            result += vec[i].first;
        }
    }
    cout << result;
}