时间复杂度：
O(log*n)，近乎是O(1)级别的
UnionFind 接口：
public interface UF {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}第一种：
//quickFind
public class UnionFind1 implements UF{
//id 这个数组中并没有存储数据的值，而是存储了数据所在的集合编号
private int[] id; public UnionFind1(int size) {
id = new int[size];
for(int i = 0 ; i < id.length ; i ++) {
id[i] = i;
}
} @Override
public int getSize() {
return id.length;
} //查找元素p所对应的集合编号
private int find(int p) {
if(p < 0 || p >= id.length) {
throw new IllegalArgumentException("p is out of bound.");
}
return id[p];
} //查看元素p和q是否属于同一个集合
@Override
public boolean isConnected(int p, int q) {
// TODO Auto-generated method stub
return find(p) == find(q);
} //将p和q所属的集合合并
@Override
public void unionElements(int p, int q) {
// TODO Auto-generated method stub
int pID = find(p);
int qID = find(q); if(pID == qID) {
return;
} for(int i = 0 ; i < id.length ; i ++) {
if(id[i] == pID) {
id[i] = qID;
}
}
} }
第二种：
//QuickUnion
//一种孩子指向父亲节的树
public class UnionFind2 implements UF{ private int[] parent; public UnionFind2(int size) {
parent = new int[size]; //初始的时候每一个节点都指向他自己，每一个节点都是一棵独立的树
for(int i = 0 ; i< size ; i ++) {
parent[i] = i;
}
} @Override
public int getSize() { return parent.length;
} private int find(int p) {
if(p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while(p != parent[p]) {
p = parent[p];
}
return p;
} @Override
public boolean isConnected(int p, int q) { return find(p) == find(q);
} @Override
public void unionElements(int p, int q) { int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot) {
return;
}else {
parent[pRoot] = qRoot;
} } }
第三种：
package UnionFind; //使树的深度尽量保持较低水平
//节点总数小的那个树去指向节点总数大的那棵树
public class UnionFind3 implements UF { private int[] parent;
// sz[i]表示以i为根的的集合中元素的个数
private int[] sz; public UnionFind3(int size) {
parent = new int[size];
for(int i = 0 ; i < parent.length ; i ++) {
parent[i] = i;
sz[i] = 1;
}
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return parent.length;
} private int find(int p) {
if(p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while(p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) { return find(p) == find(q);
} @Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot) {
return;
}
if(sz[pRoot] < sz[qRoot]) {
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else {
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
} } }
第四种：
//基于rank的优化
//使深度小的那棵树指向深度大的那棵树
public class UnionFind4 implements UF { private int[] parent;
// rank[i]表示以i为根的的集合所表示的树的层数
private int[] rank; public UnionFind4(int size) {
parent = new int[size];
for(int i = 0 ; i < parent.length ; i ++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return parent.length;
} private int find(int p) {
if(p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while(p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) { return find(p) == find(q);
} @Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot) {
return;
}
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
}else if(rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
}else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
} } }
第五种：
//路径压缩
public class UnionFind5 implements UF{ private int[] parent;
// rank[i]表示以i为根的的集合所表示的树的层数
private int[] rank; public UnionFind5(int size) {
parent = new int[size];
for(int i = 0 ; i < parent.length ; i ++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return parent.length;
} //这里添加路径压缩的过程
private int find(int p) {
if(p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while(p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) { return find(p) == find(q);
} //这里的rank不再是每个节点精准的深度，只是做为一个参考，由于性能考虑所以不维护rank
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot) {
return;
}
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
}else if(rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
}else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
} } }
第六种：
//find过程中让每个节点都指向根节点
//路径压缩
public class UnionFind6 implements UF{ private int[] parent;
// rank[i]表示以i为根的的集合所表示的树的层数
private int[] rank; public UnionFind6(int size) {
parent = new int[size];
for(int i = 0 ; i < parent.length ; i ++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
// TODO Auto-generated method stub
return parent.length;
} //这里添加路径压缩的过程
//递归调用
private int find(int p) {
if(p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
if(p != parent[p]) {
parent[p] = find(parent[p]);
}
return parent[p];
}
@Override
public boolean isConnected(int p, int q) { return find(p) == find(q);
} //这里的rank不再是每个节点精准的深度，只是做为一个参考，由于性能考虑所以不维护rank
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q); if(pRoot == qRoot) {
return;
}
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot;
}else if(rank[pRoot] > rank[qRoot]){
parent[qRoot] = pRoot;
}else {
parent[qRoot] = pRoot;
rank[pRoot] += 1;
} } }