アルゴリズム:集計(4つの方法)
3775 ワード
public class UnionFind {
private int[] id;
private int count;
public UnionFind(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}
public int getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
return id[p];
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
for(int i = 0; i < id.length; i++)
if(id[i] == pRoot) id[i] = qRoot;
count--;
}
}
public class QuickUnion {
private int[] id;
private int count;
public QuickUnion(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
}
public int getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while(p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
public class WeightedQuickUnion {
private int[] id;
private int count;
private int[] sz;
public WeightedQuickUnion(int N) {
count = N;
id = new int[N];
sz = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
public int getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
while(p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
count--;
}
public class PathCompressionWeightedQuickUnion {
private int[] id;
private int count;
private int[] sz;
public PathCompressionWeightedQuickUnion(int N) {
count = N;
id = new int[N];
sz = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
public int getCount() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
if (p != id[p]) id[p] = find(id[p]);
return id[p];
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; }
else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; }
count--;
}
}
N ( )
union() find()
union-find O(n) O(n) O(1)
quick-union O(n)
quick-union O(n) O(lgn) O(lgn)
quick-union O(n) O(1) O(1)
O(n) O(1) O(1)