Table of contents

• Problem
• Computational complexity
• Solution

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A

# Computational complexity

$O(ElogE)$ (for sorting edges)

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 10001
#define W_INF (1 << 21)

class Edge {
public:
  Int src, tgt, cost;
  Edge(Int src, Int tgt, Int cost): src(src), tgt(tgt), cost(cost) {}
  
  bool operator < ( const Edge &e) const {
    return cost < e.cost;
  }
};


class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n);
        parent.resize(n);
        for (int i=0; i<n; i++) rank[i] = 0, parent[i] = i;
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        }
    }
    
private:
    vector<int> rank;
    vector<int> parent;
    
    int root(int x) {
        if (x != parent[x]) {
            parent[x] = root(parent[x]);
        }
        
        return parent[x];
    }
};

Int N;
vector<Edge> edges;



Int kruskal() {
  Int total = 0;
  sort(edges.begin(), edges.end());
  DisjointSet dset(N);
  for (auto edge: edges) {
    if (!dset.same(edge.src, edge.tgt)) {
      total += edge.cost;
      dset.unite(edge.src, edge.tgt);
    }
  }
  return total;
}


int main(void) {
  int e, u, v, w;
  cin >> N >> e;
  while (cin >> u >> v >> w) {
    edges.push_back(Edge(u, v, w));
  }
  
  cout << kruskal() << endl;
}