[Algorithm] Minimum Spanning Tree - Kruscal

1. 최소 신장 트리(MST)를 찾는 알고리즘으로 Union-Find 아이디어를 활용한다.
2. Union-Find 란 disjoint set을 찾기 위한 아이디어 이다. 전반적인 아이디어는 다음과 같고, 알고리즘은 아래 코드에서 확인하면 된다.
   1. Union(a, b): a, b 노드가 연결되어 있다면 a 가 b를 연결시킨다. 즉, a = 1과 b=2가 연결되어 있다면 unf[a] = b 이다. 이때, unf[ ] 는 연결된 노드를 표시하기 위한 배열이고, 자기 자신을 가리키도록 초기화 된다. 즉, unf[1] = 1, unf[2]=2, unf[3]=3 .... unf[n]=n 이다.
   2. 1 과 2 노드를 Union 시키기 위해, 각 노드가 가리키는 루트노드를 찾는 Find(n) 재귀 함수를 실행한다. Find 재귀함수는 자기 자신이 루트가 되는 노드를 만나면 루트 노드를 반환한다. 즉, 1, 2가 연결되어 있을 때, unf[1]=2, unf[2]=2 이고 unf[2] 가 자기 자신을 가리키고 있으므로 2를 반환하고 Find(1) 의 루트노드는 2가 된다.
   3. Union(a, b) 내에서는 Find함수로 a와 b가 같은 루트 노드로 연결되어 있는지 먼저 확인 하는 과정을 거친다. 
   4. 만약 같은 노드로 연결되어 있지 않다면, 이 두 노드는 아직 연결되지 않았으므로 unf[a] = b 처리한다.
3. 다음으로, (노드 - 노드 - 간선 가중치) 로 들어오는 입력을 연결 리스트에 저장하고 간선 가중치에 따라 오름차순 정렬한다.
4. 연결리스트의 처음부터 끝까지 순회하며, find 함수를 통해 노드-노드 가 연결되어 있는지 확인하고, 연결되어있지 않다면 Union 시킨다. 
5. 가중치 기준으로 오름차순 정렬된 간선을 처음부터 끝까지 순회하는 동안, 루트 노드가 동일한지 확인하는 과정을 거치기 때문에 싸이클이 없는 최소신장트리를 찾을 수 있게 된다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
최소 신장 트리 (MST)
1. Kruscal 알고리즘: Union-find 알고리즘을 활용
2. Prim 알고리즘: priority-queue
*/

int unf[30];

struct Edge{
    int v1;
    int v2;
    int val;
    Edge(int a, int b, int c){
        v1=a;
        v2=b;
        val=c;
    }
    bool operator<(const Edge &b) const {
        return val<b.val;
    }
};

int Find(int v)
{
    if (v == unf[v]) return v;
    else return unf[v] = Find(unf[v]);
}

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a != b) unf[a] = b;
}

int main()
{
    // freopen("78.txt", "r", stdin);
    vector<Edge> v;
    int i, n, m, a, b, c, cnt=0, res=0;
    cin >> n >> m;
    for (i=1; i<=n; i++){
        unf[i] = i;
    }

    for (i=1; i<=m; i++){
        cin>>a>>b>>c;
        v.push_back(Edge(a, b, c));
    }
    sort(v.begin(), v.end());
    for (i=0; i<m; i++){
        int fa=Find(v[i].v1);
        int fb=Find(v[i].v2);
        // 아직 연결되지 않은 경우 추가
        if (fa != fb){
            res+=v[i].val;
            Union(v[i].v1, v[i].v2);
        }
    }

    cout << res << endl;

    return 0;
}