문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력

3 3
1 2 1
2 3 2
1 3 3

예제 출력

3

문제 풀이

최소 스패닝 트리 테스트하는 문제이다.

답안 코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V   10000

int V,E;
vector<int> adj[MAX_V+1];
vector<pair<int, pair<int,int>>> edges;

int unionGroup[MAX_V+1];

int find(int i){
    while(unionGroup[i] != i)
        i = unionGroup[i] = unionGroup[unionGroup[i]];
    return i;
}
void unionSet(int u, int v){
    u = find(u);
    v = find(v);
    unionGroup[u] = v;
}
bool isUnion(int u, int v){
    return find(u) == find(v);
}

int main(){
    scanf("%d %d", &V, &E);
    for(int i = 0; i < E; ++i){
        int u,v,w;
        scanf("%d %d %d", &u, &v, &w);
        edges.push_back(make_pair(w, make_pair(u, v)));
    }
    sort(edges.begin(),edges.end());
    for(int i = 1; i <= V; ++i)
        unionGroup[i] = i;
    
    int mst_cost = 0;
    for(int i = 0; i < edges.size(); ++i){
        auto e = edges[i].second;
        if(!isUnion(e.first, e.second)){
            mst_cost += edges[i].first;
            unionSet(e.first, e.second);
        }
    }
    
    printf("%d\n", mst_cost);
    
    return 0;
}