[3124] 최소 스패닝 트리

### SW Expert Academy - D4 ###

[3124] 최소 스패닝 트리 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE

<소스코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int f, t, w; };
 
int p[100001];
 
bool cmp(P a, P b)
{
    return a.w < b.w;
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
bool Union(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        for(int i=1; i<=v; i++)
            p[i] = i;
 
        vector<P> g;
        for(int i=0; i<e; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g.push_back((P){a, b, c});
        }
        
        sort(g.begin(), g.end(), cmp);
 
        long long ans=0LL;
        for(int i=0; i<e; i++) 
            if(Union(g[i].f, g[i].t)) 
                ans += g[i].w;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}
 

>> Union-Find 를 이용한 크루스칼 알고리즘 사용.

>> ans 값은 int 범위를 벗어남에 주의.