MST (최소스패닝 트리) / Kruskal , Union-Find 이용

/ Kruskal MST using Union Find /
1. 엣지의 가중치 값으로 오름차순 정렬
2. 작은 것부터 선택하되, ✨ 사이클이 생기지 않도록
-> 간선의 2개 정점이 같은 집합이 아닌 경우 선택한다는 뜻.
-> 선택하면 가중치 누적하고, 집합에 union 해버리기

/*
 * 모든 도시를 연결하는 최소 비용
 */


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

using namespace std;
int unf[10001]; //유니언 파인드 집합

struct Edge {
    int s;//시작 정점
    int e; //끝나는 정점
    int val; //가중치

    //생성자
    Edge(int a, int b, int c) {
        s = a;
        e = 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() {
    int n, m, a, b, c, cnt = 0, res = 0;
    vector<Edge> Ed; //간선 저장

    //unf배열 초기화 : 처음 루트는 자기 자신
    for (int i = 1; i <= n; i++) unf[i] = i;

    //엣지 읽어서 넣기
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        Ed.push_back(Edge(a, b, c));
    }

    //val 기준으로 오름차순
    sort(Ed.begin(), Ed.end());

    //각 엣지들 확인
    for (int i = 0; i < m; i++) {
        //엣지의 두 노드의 루트 찾기 -> 같은 집합인지
        int fa = Find(Ed[i].s);
        int fb = Find(Ed[i].e);

        //서로 달라서 사이클이 생기지 않으면!
        if (fa != fb) {
            res += Ed[i].val; //가중치 누적
            Union(Ed[i].s, Ed[i].e); //집합 만들기
        }
    }
    
}