algorithm_study/lib/cpp/mst.cpp at main · bccha/algorithm_study · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<algorithm>
#include<queue>
#include<tuple>
#include<vector>


usingnamespacestd;

// Union-Find 구조체 필요 (여기서는 간단히 포함)
structDSU {
 vector<int> parent;
DSU(int n) {
 parent.resize(n + 1);
for (int i = 0; i <= n; ++i)
 parent[i] = i;
 }
intfind(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
boolunite(int a, int b) {
 a = find(a);
 b = find(b);
if (a == b)
returnfalse;
 parent[b] = a;
returntrue;
 }
};

structEdge {
int u, v;
longlong weight;
booloperator<(const Edge &other) const { return weight < other.weight; }
};

// Kruskal 알고리즘
// 반환: {MST 가중치 합, 간선 수}
pair<longlong, int> kruskal(int n, vector<Edge> &edges) {
sort(edges.begin(), edges.end());
DSUdsu(n);
longlong sum = 0;
int count = 0;

for (constauto &edge : edges) {
if (dsu.unite(edge.u, edge.v)) {
 sum += edge.weight;
 count++;
 }
 }
return {sum, count};
}

// Prim 알고리즘
constlonglongINF = 1e18;
longlongprim(int n, int start,
const vector<vector<pair<int, longlong>>> &adj) {
longlong sum = 0;
 vector<bool> visited(n + 1, false);
 priority_queue<pair<longlong, int>, vector<pair<longlong, int>>, greater<>>
 pq;

 pq.push({0, start});
int count = 0;

while (!pq.empty()) {
auto [w, cur] = pq.top();
 pq.pop();

if (visited[cur])
continue;
 visited[cur] = true;
 sum += w;
 count++;

for (auto &[next, weight] : adj[cur]) {
if (!visited[next]) {
 pq.push({weight, next});
 }
 }
 }

if (count < n)
return -1; // 연결 그래프 아님
return sum;
}