| 35 | } |
| 36 | } |
| 37 | int main(){ |
| 38 | int N=5,m=6; |
| 39 | vector<node> edges; |
| 40 | edges.push_back(node(0,1,2)); |
| 41 | edges.push_back(node(0,3,6)); |
| 42 | edges.push_back(node(1,0,2)); |
| 43 | edges.push_back(node(1,2,3)); |
| 44 | edges.push_back(node(1,3,8)); |
| 45 | edges.push_back(node(1,4,5)); |
| 46 | edges.push_back(node(2,1,3)); |
| 47 | edges.push_back(node(2,4,7)); |
| 48 | edges.push_back(node(3,0,6)); |
| 49 | edges.push_back(node(3,1,8)); |
| 50 | edges.push_back(node(4,1,5)); |
| 51 | edges.push_back(node(4,2,7)); |
| 52 | sort(edges.begin(), edges.end(), comp); |
| 53 | |
| 54 | vector<int> parent(N); |
| 55 | for(int i = 0;i<N;i++) |
| 56 | parent[i] = i; |
| 57 | vector<int> rank(N, 0); |
| 58 | |
| 59 | int cost = 0; |
| 60 | vector<pair<int,int>> mst; |
| 61 | for(auto it : edges) { |
| 62 | if(findPar(it.v, parent) != findPar(it.u, parent)) { |
| 63 | cost += it.wt; |
| 64 | mst.push_back({it.u, it.v}); |
| 65 | unionn(it.u, it.v, parent, rank); |
| 66 | } |
| 67 | } |
| 68 | cout << cost << endl; |
| 69 | for(auto it : mst) cout << it.first << " - " << it.second << endl; |
| 70 | return 0; |
| 71 | } |
| 72 | |
| 73 | /* |
| 74 | Output: |