C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1197번:최소 스패닝 트리 답

가지도록 모든 노드의 level에 따른 부모를 트리의 위로 올라가면서 Find, 한 부모의 자식으로 Union 시켜줌
//가장 아래의 자식부터 합쳐진 하나의 부모노드까지의 거리가 최단거리->minimum cost
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int p[10001],n,m,u,v,x,y,cost,cnt,ans;
struct Edge {
    int start, end, cost;
    bool operator < (const Edge &other) { return cost < other.cost; }
};
int Find(int x)
{
    if (x == p[x])
        return x;
    else
        return p[x] = Find(p[x]);
}
void Union(int x, int y)//트리를 위로 올라가며 부모(y)를 x에 저장한다.
{
    x = Find(x);
    y = Find(y);
    p[x] = y;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
    }
    vector <Edge> a(m);//간선을 보고 최소 가중치를 구한다
    for (int i = 0; i < m; i++)
    {
        cin >> a[i].start >> a[i].end >> a[i].cost;
    }
    sort(a.begin(), a.end());//오름차순 정렬 cost는 낮은순으로 정렬
    for (int i = 0; i < m; i++)
    {
        Edge e = a[i];
        int x = Find(e.start);
        int y = Find(e.end);
        if (x != y)//부모가 다르다면
        {
            Union(e.start, e.end);//공통 부모를 가지도록 해줌
            ans += e.cost;
        }
    }
    cout << ans << '\n';
}