3124. 최소 스패닝 트리

3124. 최소 스패닝 트리

오랜만에 크루스칼 알고리즘을 사용해서 최소 스패닝 트리 문제를 풀어봤다.

최소 스패닝 트리는 간선을 가중치에 따라 오름차순으로 정렬하고, union-find 를 이용해서 추가할지 말지를 결정하면 된다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int p[100001];
 
int find(int a)
{
    if (a == p[a])
    {
        return a;
    }
    else
    {
        return p[a] = find(p[a]);
    }
}
void merge(int a, int b)
{
    a = find(a);
    b = find(b);
 
    if (a == b)
    {
        return;
    }
 
    p[b] = a;
 
    return;
    
}
int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int n, m;
        long long ans = 0;
        cin >> n >> m;
 
        for (int i = 0; i <= n; i++)
        {
            p[i] = i;
        }
        vector<pair<long long,pair<int,int>>> v;
 
        for (int i = 0; i < m; i++)
        {
            int from, to, w;
            cin >> from >> to >> w;
            v.push_back({ w,{from,to} });
        }
        sort(v.begin(), v.end());
 
        for (int i = 0; i <m; i++)
        {
            int a = v[i].second.first;
            int b = v[i].second.second;
            if (find(a) != find(b))
            {
                ans += v[i].first;
                merge(a, b);
            }
        }
 
 
        cout << "#" << t << " " << ans << "\n";
    }
 
 
    
    return 0;
}