data structure


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  • 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);
    	}
    }