并查集及其优化
并查集可以动态地连通两个点，可以非常快速判断两个点是否连通。假设存在 n 个节点，我们先将所有结点的 leader 标为自身；每次连接节点 i 和 j 时，我们可以将 i 的 leader 标记为 j ；每次要查询两个节点是否相连时，我们可以查找 i 和 j 的祖先是否最终为同一个。
并查集多用于无向图的关系判断。例如冗余连接中，需要删除一条边，来将有环无向图转换为无环无向图。循环遍历每条边，如果两个节点有共同的祖先，则删除该边即可。
简单并查集
public class UnionFind {
int[] leader;
int count;
public UnionFind() {}
public UnionFind(int size) {
this.leader = new int[size];
this.count = n;
for (int i = 1; i < size; ++i) {
leader[i] = i;
}
}
public int getCount() {
return this.count;
}
public int find(int idx) {
while (idx != leader[idx]) {
idx = leader[idx];
}
return idx;
}
public void union(int idx1, int idx2) {
int ld1 = find(idx1), ld2 = find(idx2);
if (ld1 == ld2) return;
leader[ld1] = find(ld2);
--count;
}
}
对简单并查集进行优化
由于并查集是一颗树，查找效率和树高有关，尽量要保证树的高度低。
对简单并查集优化主要有两个方向：路径压缩、按秩合并。
路径压缩
理想情况：父节点下面直接连接着其子节点，且所有子节点都是叶子节点。
迭代方式：没有对中间节点的做leader节点做更新。
递归方式：修改了中间所有节点的leader节点。
public class UnionFind {
//省略
public int find1(int idx) {
while (idx != leader[idx]) {
idx = leader[idx];
}
return idx;
}
public int find2(int idx) {
if (idx != leader[idx]) {
leader[idx] = find(leader[idx]);
}
return leader[idx];
}
}
按秩合并
秩：以当前节点为根的树的高度上限。秩初始化为0，合并两颗树时，对比他们的秩，秩较大的树为新的根节点，新父节点秩 += 1;
在union时，将秩小的树合并到秩大的树上。
只有根节点的秩有意义，非根节点的秩没有意义。
虽然秩由高度决定，但是我们不直接记录高度，因为树的高度在查找过程中可能会变。但秩代表的是上限，是不会变的，所以记录秩是更高效的做法。
public class UnionFind {
public int[] leader;
public int[] rank;
public int count;
public UnionFind() {}
public UnionFind(int size) {
this.count = size;
this.leader = new int[size];
this.rank = new int[size];
for (int i = 1; i < size; ++i) {
leader[i] = i;
}
}
//省略
public void union(int idx1, int idx2) {
int ld1 = find(idx1), ld2 = find(idx2);
if (ld1 == ld2) return;
if (rank[ld1] < rank[ld2]) {
leader[ld1] = ld2;
} else if (rank[ld1] > rank[ld2] {
leader[ld2] = ld1;
} else {
leader[ld1] = ld2;
rank[ld2] += 1;
}
--count;
}
}
最终优化版
public class UnionFind {
public int[] leader;
public int[] rank;
public int count;
public UnionFind(int size) {
this.leader = new int[size];
this.rank = new int[size];
this.count = size;
for (int i = 1; i < size; ++i) {
leader[i] = i;
}
}
public int getCount() {
return this.count;
}
public int find(int idx) {
if (idx != leader[idx]) {
leader[idx] = find(leader[idx]);
}
return leader[idx];
}
public void union(int idx1, int idx2) {
int ld1 = find(idx1), ld2 = find(idx2);
if (ld1 == ld2) return;
if (rank[ld1] < rank[ld2]) {
leader[ld1] = ld2;
} else if (rank[ld1] > rank[ld2]) {
leader[ld2] = ld1;
} else {
leader[ld1] = ld2;
++rank[ld2];
}
--count;
}
}