UnionFindさえあれば，結構簡単に実装できるのね．

ただ，正しく動くかほとんど確認していないので，バグがあるかも． 

// disjoint_set.h
#include <iostream>

using namespace std;

class UnionFind {
private:
  int *root, *rank;  // root < 0 のときはサイズの情報
public:
  UnionFind(const int &n) {
    root = new int[n], rank = new int[n];
    fill_n(root, n, -1), fill_n(rank, n,  0);
  }
  int find(const int &x) {
    if (root[x] < 0) return x;
    return root[x] = find(root[x]);
  }
  void unionSet(const int &x, const int &y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rank[px] > rank)
      root[px] += root, root = px;
    else if (rank[px] < rank)
      root += root[px], root[px] = py;
    else  //if (rank[px] == rank)
      root[px] += root, root = px, rank[px]++;
  }
};

//kruskal.cpp
#include <queue>
#include "disjoint_set.h"
#include "graph.h"

template <class T>
EdgeList kruskal(const Graph &g, const EdgeProperty<T> &w) {
  const int n = g.succ.size();
  UnionFind u(n);
  typedef pair<T, Edge> TE;
  priority_queue<TE, vector<TE>, greater<TE> > q;
  for (Vertex i = 0; i < n; ++i) foreach(Vertex j, g.succ[i])
    if (i < j) q.push(TE(w(i, j), Edge(i, j)));
  EdgeList t;
  while (t.size() < n-1 && !q.empty()) {
    const Edge e = q.top().second;
    q.pop();
    if (u.find(e.first) != u.find(e.second))
      t.push_back(e), u.unionSet(e.first, e.second);
  }
  return t;
}

int main() {
  const int n = 4;
  Graph g(n);
  EdgeProperty<int> w;
  w[g.add_edge(0, 1)] = 3;
  w[g.add_edge(1, 0)] = 3;
  w[g.add_edge(0, 2)] = 2;
  w[g.add_edge(2, 0)] = 2;
  w[g.add_edge(1, 2)] = 1;
  w[g.add_edge(2, 1)] = 1;
  w[g.add_edge(0, 3)] = 0;
  w[g.add_edge(3, 0)] = 0;
  w[g.add_edge(3, 2)] = 1;
  w[g.add_edge(2, 3)] = 1;
  EdgeList mst = kruskal<int>(g, w);
  foreach(Edge e, mst)
    cout << e.first << " -> " << e.second << endl;
}