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

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

1197번: 최소 스패닝 트리

 

1. 풀이

정직한 최소 스패닝 트리 문제

https://dmzld.tistory.com/34

[자료구조] 3. Graph : MST, 최단거리, Union-Find

이전에 올린 관련 이론 정리

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

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

int V, E, A, B, C;
int p[10001];
priority_queue<info, vector<info>, comp> pq;
int res;

int find(int x) {
	if (p[x] == x)
		return x;
	else
		return p[x] = find(p[x]);
}

void merge(int x, int y) {
	int px = find(x);
	int py = find(y);

	p[max(px, py)] = min(px, py);
}

int main() {

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

	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		cin >> A >> B >> C;
		pq.push({ A, B, C });
	}

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

	while (!pq.empty()) {
		info tmp = pq.top();
		pq.pop();

		if (find(tmp.a) == find(tmp.b))
			continue;
		else {
			merge(tmp.a, tmp.b);
			res += tmp.c;
		}
	}

	cout << res;

	return 0;
}

다른 블로그 찾아봤는데 굳이 pq 안쓰고 vector, sort로 풀이하시더라