fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. vector <int> pred(0);
  6. int root(int x){
  7.     if (pred[x]==x){
  8.         return x;
  9.     }
  10.     else{
  11.         int r=root(pred[x]);
  12.         pred[x]=r;
  13.         return r;
  14.     }
  15.  
  16. }
  17. bool issame(int a,int b){
  18.     return root(a) == root(b);
  19. }
  20. void join(int a,int b){
  21.     a=root(a);
  22.     b=root(b);
  23.     if (a%2==0){
  24.         pred[a]=b;
  25.     }
  26.     else{
  27.         pred[b]=a;
  28.     }
  29. }
  30. int main()
  31. {
  32.     int n,m,k=0,rez=0;
  33.     cin >>n >> m;
  34.     vector <pair <int ,pair<int,int>>> edges;
  35.     for(int i=0;i<m;i++){
  36.         int a1,a2,v;
  37.         cin >> a1 >> a2 >> v;
  38.         edges.push_back({v,{a1,a2}});
  39.     }
  40.     sort(edges.begin(),edges.end());
  41.     for (int i=0;i<n;i++){
  42.         pred.push_back(i);
  43.     }
  44.     for (int i=0;i<n;i++){
  45.         int a,b;
  46.         a=edges[i].second.first;
  47.         b=edges[i].second.second;
  48.         cout << issame(a,b) <<' '<<  root(a) <<' '<< root(b) << endl;
  49.         if (! issame(a,b)){
  50.             k++;
  51.             rez +=edges[i].first;
  52.             join(a,b);
  53.             if (k==n-1){
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.     cout << rez;
  59.     return 0;
  60. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin
copy 
3 3
1 2 1
2 3 2
3 1 3
stdout
copy 
0 1 2
0 1 0
3
https://ideone.com/qDkkXv
language:
C++ (gcc 8.3)
created:
4 years 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!