fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 +5;
  4. long long n,m;
  5. pair<long long,pair<long long, long long>> pr[MaxN];
  6. struct DSU
  7. {
  8.     long long lab[MaxN];
  9.     void init()
  10.     {
  11.         for (long long i=1; i<=n; i++)
  12.         {
  13.             lab[i]=-1;
  14.         }
  15.     }
  16.     long long get_root(long long u)
  17.     {
  18.         if(lab[u]<0) return u;
  19.         return lab[u]=get_root(lab[u]);
  20.     }
  21.     void unite(long long u , long long v)
  22.     {
  23.         long long x = get_root(u), y=get_root(v);
  24.         if(x==y)
  25.         {
  26.             return;
  27.         }
  28.         if(lab[x]>lab[y]) swap(x,y);
  29.         lab[x]+=lab[y];
  30.         lab[y]=x;
  31.         return;
  32.     }
  33.     bool check(long long u, long long v)
  34.     {
  35.         return get_root(u)==get_root(v);
  36.     }
  37.     long long get_size(long long u)
  38.     {
  39.         return -lab[get_root(u)];
  40.     }
  41. };
  42. DSU dsu;
  43. void input()
  44. {
  45.     cin >> n >> m;
  46.     for (long long i=1; i<=m; i++)
  47.     {
  48.         cin >> pr[i].second.first >> pr[i].second.second >> pr[i].first;
  49.     }
  50. }
  51. void solve()
  52. {
  53.     dsu.init();
  54.     long long ans=0;
  55.     sort (pr+1, pr+m+1);
  56.     for (long long i=1; i<=m; i++)
  57.     {
  58.         long long u = pr[i].second.first;
  59.         long long v = pr[i].second.second;
  60.         long long w = pr[i].first;
  61.         if(!dsu.check(u,v))
  62.         {
  63.             dsu.unite(u,v);
  64.             ans+=w;
  65.         }
  66.     }
  67.     cout << ans;
  68. }
  69. int main()
  70. {
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     input();
  74.     solve();
  75. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YAJiWG
language:
C++14 (gcc 8.3)
created:
4 hours 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!