fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4.  
  5. int parent[N],sz[N];
  6.  
  7. void make(int v){
  8. parent[v] = v;
  9. sz[v]=1;
  10. }
  11.  
  12. int find(int v){
  13. if(v == parent[v]) return parent[v];
  14. //path compression
  15.  parent[v]=find(parent[v]);
  16. return parent[v];
  17.  
  18. }
  19.  
  20. void Union(int a, int b){
  21.     a=find(a);
  22.     b=find(b);
  23.     if(a!=b){
  24.         //union by size
  25.         if(sz[a]<sz[b])swap(a,b);
  26.         parent[b]=a;
  27.         sz[a]+=sz[b];
  28. }
  29. }
  30.  
  31.  
  32.  
  33. int main()
  34. {
  35.     int n,m;
  36.     cin>>n>>m; //number of nodes and edges
  37.     vector<pair<int,pair<int,int> > >edges;// weight and nodes of edges
  38.     for( int i=0;i<m;i++){
  39.      int u,v,wt;
  40.      cin>>u>>v>>wt;
  41.      edges.push_back({wt, {u,v}});
  42.     }
  43.     sort(edges.begin(),edges.end());
  44.     for(int i=0;i<=n;i++)make(i);
  45.  
  46.     int total_cost=0;
  47.     for(auto &edge:edges){
  48.         int wt=edge.first;
  49.         int u=edge.second.first; //u and v are nodes
  50.         int v=edge.second.second;// u and v are nodes
  51.        if(find(u)==find(v)) continue; //find parents of u and v and if they are same then continue the loop
  52.        Union(u,v);// union of u and v 
  53.        total_cost+=wt; //add weight of edge to total cost
  54.        cout<<u<<" "<<v<<endl;
  55.     }
  56.     cout<<total_cost<<endl;
  57.  
  58.  
  59. }
  60.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5  7
A B 2
A D 6
B C 3
B D 8
B E 5
C E 7
D E 9
stdout
copy 
0
https://ideone.com/QuCkkb
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!