알고리즘/알고리즘
[C++]백준 1197번 : 최소 스패닝 트리
두둠칫
2021. 9. 9. 06:01
https://www.acmicpc.net/problem/1197
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
1. 풀이
정직한 최소 스패닝 트리 문제
[자료구조] 3. Graph : MST, 최단거리, Union-Find
0. Graph 노드들과 그 노드들을 연결한 간선에 대한 정보를 저장하는 자료구조 1. Terminology 1) vertex(정점), edge(간선) 2) degree : 한 정점에 간선으로 연결된 정점 개수 2-1) in-degree : 방향 그래프에..
dmzld.tistory.com
이전에 올린 관련 이론 정리
#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로 풀이하시더라