并查集
由孩子指向父亲，快速判断节点连接状态。可用于解决连接问题，就集合的并集。
集合
//interface
public interface UnionFind {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}
public class UnionFind1 implements UnionFind {
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是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//合并元素p与元素q所属的集合 O(n)
@Override
public void unionElements(int p, int q) {
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;
}
}
}
//时间复杂度 O(log^*n) 近乎于O(1)
优化一
孩子指向父亲，依然用数组表示，但是形成的是树结构。
union
仍然可以使用数组表示
初始状态
union
public class UnionFind2 implements UnionFind {
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;
}
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
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;
}
//O(h)复杂度，h为树的高度
//查看元素p与q是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)复杂度，h为树的高度
//合并元素p与元素q所属的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
parent[pRoot] = parent[qRoot];
}
}
优化二
让节点个数少的根节点指向节点个数多的根节点。
优化二
public class UnionFind3 implements UnionFind {
private int[] parent;
private int[] sz;
public UnionFind3(int size) {
parent = new int[size];
//sz[i]表示以i为根的集合中元素个数
sz = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
sz[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
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;
}
//O(h)复杂度，h为树的高度
//查看元素p与q是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)复杂度，h为树的高度
//合并元素p与元素q所属的集合 O(n)
@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] = parent[qRoot];
sz[qRoot] += sz[pRoot];
}
else { // sz[pRoot] >= sz[qRoot]
parent[qRoot] = parent[pRoot];
sz[pRoot] += sz[qRoot];
}
}
}
//时间复杂度 O(log^*n) 近乎于O(1)
优化三
基于rank的优化，rank[i]表示根节点为i的树的高度。
让深度比较少的树向深度比较高的树进行合并。
优化三
public class UnionFind4 implements UnionFind {
private int[] parent;
private int[] rank;
public UnionFind4(int size) {
parent = new int[size];
//rank[i]表示以i为根的集合所表示的树的层数
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
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;
}
//O(h)复杂度，h为树的高度
//查看元素p与q是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)复杂度，h为树的高度
//合并元素p与元素q所属的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根据俩个元素所在树的rank不同判断合并方向
//将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//时间复杂度 O(log^*n) 近乎于O(1)
优化四
路径压缩，将高树压缩成矮树
优化四
4.1
4.2
4.3
public class UnionFind5 implements UnionFind {
private int[] parent;
private int[] rank;
public UnionFind5(int size) {
parent = new int[size];
//rank[i]表示以i为根的集合所表示的树的层数
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = I;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
// 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;
// }
//优化 路径压缩 经典优化思路
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
private int find(int p) {
if (p < 0 && p >= parent.length)
throw new IllegalArgumentException("p is out of bound");
//没有改变rank 使用粗略的rank值已经能满足性能
while (p != parent[p])
parent[p] = parent[parent[p]];
p = parent[p];
return p;
}
//O(h)复杂度，h为树的高度
//查看元素p与q是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)复杂度，h为树的高度
//合并元素p与元素q所属的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根据俩个元素所在树的rank不同判断合并方向
//将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//时间复杂度 O(log^*n) 近乎于O(1)
优化五
使用递归，将查询的节点，以及其之前的节点都直接指向跟节点
优化五
public class UnionFind6 implements UnionFind{
private int[] parent;
private int[] rank;
public UnionFind6(int size) {
parent = new int[size];
//rank[i]表示以i为根的集合所表示的树的层数
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize() {
return parent.length;
}
//优化 路径压缩 经典优化思路
//查找过程，查找元素p所对应的集合编号
//O(h)复杂度，h为树的高度
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];
}
//O(h)复杂度，h为树的高度
//查看元素p与q是否属于同一个集合 O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//O(h)复杂度，h为树的高度
//合并元素p与元素q所属的集合 O(n)
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
//根据俩个元素所在树的rank不同判断合并方向
//将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = parent[qRoot];
} else if (rank[pRoot] > rank[qRoot]) {
parent[qRoot] = parent[pRoot];
}
else { // =
parent[qRoot] = parent[pRoot];
rank[pRoot] += 1;
}
}
}
//时间复杂度 O(log^*n) 近乎于O(1)
