forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathkruskal.cc
More file actions
67 lines (62 loc) · 1.29 KB
/
kruskal.cc
File metadata and controls
67 lines (62 loc) · 1.29 KB
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
//
// Minimum Spanning Tree (Kruskal)
//
//
// Description
// Finding minimum spanning tree.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
struct edge {
int src, dst;
int weight;
};
struct graph {
int n;
vector<edge> edges;
graph(int n = 0) : n(n) { }
void add_edge(int src, int dst, int weight) {
n = max(n, max(src, dst)+1);
edges.push_back({src, dst, weight});
}
vector<int> p;
int root(int i) {
return p[i] < 0 ? i : p[i] = root(p[i]);
}
bool unite(int i, int j) {
if ((i = root(i)) == (j = root(j))) return false;
if (p[i] > p[j]) swap(i, j);
p[i] += p[j]; p[j] = i;
return true;
}
int kruskal() {
p.assign(n, -1);
sort(all(edges), [](edge x, edge y) {
return x.weight < y.weight;
});
int result = 0;
for (auto e: edges)
if (unite(e.src, e.dst))
result += e.weight;
return result;
}
};
graph random_graph(int n, int d) {
graph g(n);
for (int i = 0; i < n; ++i) {
for (int k = 0; k < d; ++k) {
int j = rand() % n;
g.add_edge(i, j, rand() % n);
}
}
return g;
}
int main() {
auto g = random_graph(100000, 100);
cout << "[kruskal] " << g.kruskal() << endl;
}