[C++] 백준 1197번 최소 스패닝 트리

그래프의 정점을 최소 가중치로 모두 이어주는 문제입니다.

최소 스패닝 트리는 프림 알고리즘과, 크루스칼 알고리즘으로 풀수있습니다.

크루스칼 알고리즘을 통해서 풀어보았습니다.
가중치가 작은 간선부터 연결해주며, 연결된 정점들은 부모를 동일시 시켜줍니다.
부모가 같을경우 간선을 연결하면 싸이클이 생기므로,
부모가 같지 않을때만 가중치를 기준으로 연결해주면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char *argv[])
{
	int p, c;
	int V, E;
	int A, B, C;
	int parent[10010];
	long long weightSum = 0;
	priority_queue<pair<int, pair<int, int> > > pq;
	
	memset(parent, 0, sizeof(parent));

	scanf("%d", &V);
	scanf("%d", &E);

	for (int i = 1; i <= V; ++i) {
		parent[i] = i;
	}

	for (int i = 1; i <= E; ++i) {
		scanf("%d", &A);
		scanf("%d", &B);
		scanf("%d", &C);

		pq.push(make_pair(-C, make_pair(A, B)));
	}

	while (!pq.empty()) {
		int a = pq.top().second.first;
		int b = pq.top().second.second;

		p = min(parent[a], parent[b]);
		c = max(parent[a], parent[b]);

		if (p == c) {
			pq.pop();
			continue;
		}

		for (int i = 1; i <= V; ++i) {
			if (parent[i] == c) {
				parent[i] = p;
			}
		}

		weightSum += -pq.top().first;
		pq.pop();
	}

	printf("%lld\n", weightSum);

	return 0;
}