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;
}
```