forked from ritikbanger/Hacktoberfest2022-DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
kruskals.cpp
66 lines (62 loc) · 1.47 KB
/
kruskals.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;
struct edge{
int u, v, w;
edge(int a, int b, int c){
u=a;v=b;w=c;
}
};
bool sortbywt(struct edge a, struct edge b){
return a.w < b.w;
}
int find(int u, vector<int> &parent){
if(parent[u]==u)return u;
return parent[u]=find(parent[u], parent);
}
void Union(int u, int v, vector<int> &rank, vector<int> &parent){
int a = find(u, parent);
int b = find(v, parent);
if(rank[a]<rank[b]){
parent[a]=b;
}
else if(rank[b]<rank[a]){
parent[b]=a;
}
else {
parent[b]=a;
rank[a]++;
}
}
int main(){
int E,V;
cin >> E >> V;
vector<edge> edges;
for(int i=0;i<E;i++){
int u,v,w;
cin >> u >> v >> w;
edges.push_back(edge(u,v,w));
}
vector<int> parent(V);
vector<int> rank(V);
for(int i=0;i<V;i++){
parent[i]=i;
rank[i]=0;
}
sort(edges.begin(), edges.end(), sortbywt);
vector<edge> mst;
int cost=0;
for(edge x: edges){
if(find(x.u, parent)!=find(x.v, parent)){
mst.push_back(x);
cost+=x.w;
Union(x.u, x.v, rank, parent);
}
}
cout <<"Minimum Spanning Tree:"<<endl;
cout <<"Minimum cost: "<<cost<<endl;
cout <<"V1 V2 WT:"<<endl;
for(int i=0;i<mst.size();i++){
cout <<mst[i].u<<" "<<mst[i].v<<" "<<mst[i].w<<endl;
}
return 0;
}