Tag. Union Find
- 基础知识
1. 好介绍： http://blog.csdn.net/dm_vincent/article/details/7655764
2. 模板class UF
class UF {
private int[] id, size;
private int count;
public UF (int N) {
count = N;
id = new int[N]; //represent the root.
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}
public int count() {
return count;
}
public int find(int p) {
while (p != id[p]) {
id[p] = id[id[p]]; // find the root of p
p = id[p];
}
return p;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int i = id[p];
int j = id[q];
if (i == j)
return ;
if (size[i] < size[j]) {
id[i] = j;
size[j] += size[i];
}
else {
id[j] = i;
size[i] += size[j];
}
count--;
}
}