クラスカル法をJavaで書く．

蟻本見ながら書いた．二つくらいの問題でちゃんと動いたのでたぶん合ってると思う．

コード

static class Kruskal {
	int n;
	List<int[]> edges;

	public Kruskal(int n) {
		this.n = n;
		edges = new ArrayList<int[]>();
	}

	void addEdge(int u, int v, int cost) {
		edges.add(new int[] { u, v, cost });
	}

	List<int[]> getEdges() {
		Collections.sort(edges, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});
		UnionFind uf = new UnionFind(n);
		List<int[]> result = new ArrayList<int[]>();
		for (int[] edge : edges) {
			if (!uf.isSame(edge[0], edge[1])) {
				uf.unite(edge[0], edge[1]);
				result.add(edge);
			}
		}
		return result;
	}
}

static class UnionFind {
	int[] par;
	int[] rank;

	public UnionFind(int n) {
		par = new int[n];
		rank = new int[n];
		for (int i = 0; i < n; ++i) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		return (par[x] == x) ? x : (par[x] = find(par[x]));
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;
		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y])
				++rank[x];
		}
	}

	boolean isSame(int x, int y) {
		return find(x) == find(y);
	}
}

使い方

・SPOJ 3188 "Minimum Spanning Tree"

public static void main(String[] args) throws Exception{
	Kruskal k = new Kruskal(next());
	for(int m = next();m-->0;){
		k.addEdge(next()-1, next()-1, next());
	}
	long sum = 0;
	for(int[] i : k.getEdges()){
		sum += i[2];
	}
	System.out.println(sum);
}

・Topcoder SRM 492 hard "TimeTravellingSalesman"
bidirectedで書いてるけど関係ないかも．

public long determineCost(int N, String[] roads) {
	Kruskal k = new Kruskal(N);
	for(String str : concat(roads).split(" ")){
		String[] strs = str.split(",");
		int u = new Integer(strs[0]), v = new Integer(strs[1]), c = new Integer(strs[2]);
		k.addEdge(u, v, c);
		k.addEdge(v, u, c);
	}
	long r = 0;
	List<int[]> edges = k.getEdges();
	if(edges.size() != N - 1){
		return -1;
	}
	for(int[] is : edges){
		r += is[2];
	}
	return r;
}