[C++]백준 1992번 : 네트워크연결

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

1. 접근, 풀이

모든 node를 대상으로 최소스패닝트리를 구하는 문제로 edge의 정보가 주어진다.

따라서 edge 기준으로 그래프의 최소스패닝트리를 구할 수 있는 크루스칼 알고리즘을 적용했다.

union&find에서 더 작은 node를 parent로 선택했다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <stack>

using namespace std;

struct state{
	int a, b, c;
};

struct comp{
	bool operator()(state a, state b){
		return a.c > b.c;
	}
};

int ans = 0;

int N, M, a, b, c;
priority_queue<state, vector<state>, comp> pq;
vector<state> res;
int p[1001];

int find(int n){
	while (n != p[n])
		n = p[n];
	return n;
}

bool uni(state s){
	int ca = find(s.a), cb = find(s.b);
	
	if (ca == cb)
		return false;

	p[max(ca, cb)] = min(ca, cb);

	return true;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		p[i] = i;

	for (int i = 0; i < M; i++){
		cin >> a >> b >> c;
		pq.push({ a, b, c });
	}

	while (!pq.empty() && res.size() < N){
		state tmp = pq.top();
		pq.pop();

		if (uni(tmp)){
			res.push_back(tmp);
		}
	}

	while (!res.empty()){
		ans += res.back().c;
		res.pop_back();
	}

	cout << ans;

	return 0;
}