/
Kruskal.cpp
66 lines (65 loc) · 2.08 KB
/
Kruskal.cpp
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
#include<bits/stdc++.h>
using namespace std;
class KruskalAlgo {
vector<int> parent;
vector<int> sizes;
public :
vector<list<int>> mstPath;
KruskalAlgo(int size) {
parent.resize(size);
sizes.resize(size);
mstPath.resize(size);
}
void make(int a) {
parent[a] = a;
sizes[a] = 1;
}
int find(int a) {
if(a == parent[a]) return a;
return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) {
if(sizes[a] < sizes[b]) {
swap(a,b);
}
parent[b] = a;
sizes[a] += sizes[b];
}
}
static bool compare(vector<int> r1, vector<int> r2) {
if(r1[2] < r2[2]) return true;
return false;
}
void mst(vector<vector<int>> edges, int vertices) {
for(int i=0; i<vertices; i++) make(i);
sort(edges.begin(), edges.end(), compare);
for(int i=0; i<edges.size(); i++) {
cout<<edges[i][0]<<" - "<<edges[i][1]<<" with weight "<<edges[i][2]<<endl;
}
for(int i=0; i<edges.size(); i++) {
cout<<"in dsu "<<endl;
if(find(edges[i][0]) != find(edges[i][1])) {
cout<<"taking edges "<<edges[i][0]<<" and "<<edges[i][1]<<endl;
Union(find(edges[i][0]), find(edges[i][1]));
mstPath[edges[i][0]].push_back(edges[i][1]);
}
}
}
};
int main() {
int vertices = 6;
vector<vector<int>> edges = {{0,1,2}, {1,2,3}, {2,3,5}, {3,4,9}, {3,0,1}, {0,4,4}, {1,3,3}, {1,5,6}, {5,2,7}};
KruskalAlgo ka(vertices);
ka.mst(edges, vertices);
for(int i = 0; i<ka.mstPath.size(); i++) {
cout<<"Path from "<<i<<" to ";
for(auto it = ka.mstPath[i].begin(); it != ka.mstPath[i].end(); it++) {
cout<<*it<<"->";
}
cout<<endl;
}
return 0;
}