백준 1197번 최소 스패닝 트리 [C++]

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

1197번: 최소 스패닝 트리

 

#문제 간단 정리

최소 스패닝 트리를 구현하는되는 문제

즉 크루스칼 알고리즘이랑 

프림 알고리즘을 구현하면 되는 문제이다

https://yabmoons.tistory.com/191

[ 백준 1197 ] 최소 스패닝 트리 (C++)

 

이 블로그에 크루스칼이 잘 정리 되어있으니까 모른다면 참고하면 좋을 것 같다. 

#문제 해결 방법

유니온 파인드를 우선 구현하고 그 이후에 

크루스칼을 구현하면 된다.

#전체 코드

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

#define MAX 10001


int Parent[MAX];

vector<pair<int, pair<int, int>>> V;

int Find(int x) {
    if (Parent[x] == 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;
    else return false;
}

int main() {
    
    int Vertex, E, Answer=0;

    cin >> Vertex >> E;
    for (int i = 0; i < E; i++) {
        int From, To, Cost;
        cin >> From >> To >> Cost;

        V.push_back(make_pair(Cost, make_pair( From,To )));
    }

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

    for (int i = 1; i <= Vertex; i++) {
        Parent[i] = i;
    }

    for (int i = 0; i < E; i++) {
        if (SameParent(V[i].second.first, V[i].second.second) == false) {
            Union(V[i].second.first, V[i].second.second);
            Answer = Answer + V[i].first;
        }
    }

    cout << Answer << '\n';

    return 0;
}