[Gold 4] 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

 

이 문제는 스패닝 트리를 생성할 때 가중치의 합을 구하면 된다.

 

스패닝 트리는 크루스칼 알고리즘을 사용해 구현하였다.

union - find를 사용해 스패닝 트리를 생성할 수 있었다.

 

부모가 같지 않다는 것은 스패닝 트리를 만들 수 있는 조건에 해당하기 때문에

answer에 가중치를 누적하면 된다.

 

부모가 같지 않는지 확인하는 것은 find함수를 사용한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int V, E;
int parent[10001];
vector<pair<int,pair<int,int>>> costs;
int answer = 0;

int find(int x) {
	if (parent[x] == x)return x;
	else return parent[x] = find(parent[x]); 
}
void uni(int x, int y) {
	x = find(x); 
	y = find(y); 
	parent[y] = x; 
}
bool isSame(int x, int y) {
	x = find(x); 
	y = find(y); 
	if (x == y)return true;
	else return false; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>V>>E;

    int A, B, C;
    for(int i = 0;i<E;i++){
        cin>>A>>B>>C;
        costs.push_back({C, {A,B}});
    }
    sort(costs.begin(), costs.end());
    for(int i = 1;i<=V;i++)
        parent[i] = i;
    
    for(int i = 0;i<costs.size();i++){
        if(!isSame(costs[i].second.first, costs[i].second.second)){
            uni(costs[i].second.first, costs[i].second.second);
            answer += costs[i].first;
        }
    }
    cout<<answer;
}