data structure - procom @ ウィキ

• union find木

  class UnionFind {
  	int[] par;
  	int[] rank;
  	int n;
   
  	UnionFind(int n) {
  		par = new int[n];
  		rank = new int[n];
  		this.n = n;
  		for (int i = 0; i < n; i++)
  			par[i] = i;
  	}
   
  	//木の根を求める
  	//0<=x<nでないのとき-1を返す
  	int find (int x) {
  		if (x < 0 || n <= x) return -1;
  		if (par[x] == x) 
  			return x;
  		else 
  			return par[x] = find(par[x]);
  	}
   
  	//xとyの属する集合を併合
  	//範囲外のとき-1を返す．それ以外は0を返す．
  	int unite (int x, int y) {
  		if (x < 0 || n <= x || y < 0 || n <= y) return -1;
  		x = find(x);
  		y = find(y);
  		if (x == y) return 0;
   
  		if (rank[x] < rank[y]) {
  			par[x] = y;
  		} else {
  			par[y] = x;
  			if (rank[x] == rank[y]) rank[x]++;
  		}
  		return 0;
  	}
   
  	//xとyが同じ集合に属するか否か
  	boolean same(int x, int y) {
  		return find(x) == find(y);
  	}
  }