「data structure」の編集履歴（バックアップ）一覧はこちら

「data structure」(2013/10/07 (月) 22:37:02) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

-union find木
#highlight(java){{
	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);
	}
}	
}}

-隣接リスト(有向グラフ，重みなし)
#highlight(java){{
class AdjacencyList {
	
	private class Node {
		HashSet<Integer> to = new HashSet<Integer>();
	}
	
	int n;
	private Node[] nodes;
	
	AdjacencyList(int n) {
		this.n = n;
		nodes = new Node[n];
		for (int i = 0; i < n; i++)
			nodes[i] = new Node();
	}
	
	//xからyに辺を張る
	void add(int x, int y) {
		nodes[x].to.add(y);
	}
	
	//xからyに辺があるか判定
	boolean isEdge(int x, int y) {
		return nodes[x].to.contains(y);
	}
	
	//頂点xのiterator
	Iterator<Integer> iterator(int x) {
		return nodes[x].to.iterator();
	}

}
}}

-隣接リスト(無向グラフ，重みなし)
#highlight(java){{
class AdjacencyList {
	
	private class Node {
		HashSet<Integer> to = new HashSet<Integer>();
	}
	
	int n;
	private Node[] nodes;
	
	AdjacencyList(int n) {
		this.n = n;
		nodes = new Node[n];
		for (int i = 0; i < n; i++)
			nodes[i] = new Node();
	}
	
	//xからyに辺を張る
	void add(int x, int y) {
		nodes[x].to.add(y);
		nodes[y].to.add(x);
	}
	
	//xからyに辺があるか判定
	boolean isEdge(int x, int y) {
		return nodes[x].to.contains(y);
	}
	
	//頂点xのiterator
	Iterator<Integer> iterator(int x) {
		return nodes[x].to.iterator();
	}

}
}}

-隣接リスト(有向グラフ，重みあり)
#highlight(java){{
class AdjacencyList {
	
	class Edge {
		int to;
		int cost;
		Edge(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}
	}
	
	private class Node {
		HashSet<Edge> edge = new HashSet<Edge>();
	}
	
	int n;
	private Node[] nodes;
	
	AdjacencyList(int n) {
		this.n = n;
		nodes = new Node[n];
		for (int i = 0; i < n; i++)
			nodes[i] = new Node();
	}
	
	//xからyに辺を張る
	void add(int x, int y, int cost) {
		nodes[x].edge.add(new Edge(y, cost));
	}
	
	//頂点xのiterator
	Iterator<Edge> iterator(int x) {
		return nodes[x].edge.iterator();
	}

}
}}

-union find木
#highlight(java){{
	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);
	}
}	
}}