graph.kruskal

graph.kruskal.cc

/// {{{
struct UnionFind {
  vector<int> table;
  UnionFind(int size) : table(size, -1) {}
  int root(int x) {
    if (table[x] < 0) return x;
    table[x] = root(table[x]);
    return table[x];
  }
  bool merge (int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (table[y] < table[x]) swap(x, y);
      table[x] += table[y]; table[y] = x;
    }
    return x != y;
  }
};
/// }}}

int kruskal(int n, vvi&adj, vvi&cost) {
  int total = 0;
  UnionFind uf(n);
  using Edge = tuple<int, int, int>; // cost, from, to
  priority_queue<Edge, vector<Edge>, greater<Edge>> q; // minimize
  rep (u, n) {
    for (int v: adj[u]) {
      q.push(make_tuple(cost[u][v], u, v));
    }
  }
  while (not q.empty()) {
    Edge e = q.top(); q.pop();
    int c = get<0>(e);
    int u = get<1>(e),
        v = get<2>(e);
    if (uf.root(u) == uf.root(v)) continue;
    uf.merge(u, v);
    total += c;
  }
  return total;
}

Example

using vi = vector<int>;
using vvi = vector<vi>;
int main() {

  // this graph is an example
  // on the page: http://ja.wikipedia.org/wiki/プリム法
stringstream input(
"  7"
"  0 1 7"
"  0 3 5"
"  1 2 8"
"  1 3 9"
"  1 4 7"
"  2 4 5"
"  3 4 15"
"  3 5 6"
"  4 5 8"
"  4 6 9"
"  5 6 11");
  int answer = 39;
  
  {
    int n; input >> n;
    vvi adjacency_list(n);
    vvi cost_table(n, vi(n, inf));
    loop {
      int a, b, c; input >> a >> b >> c;
      if (not input) break;
      adjacency_list[a].push_back(b);
      adjacency_list[b].push_back(a);
      cost_table[a][b] = cost_table[b][a] = c;
    }
    assert(kruskal(n, adjacency_list, cost_table) == answer);
  }
  return 0;
}