我们使用一个 int 数组来表示每一个节点所在的集合。如 节点0 所在的集合标记由 id[0] 来存储。由于初始状态下，每一个节点都是一个独立的节点，那么 N 个节点就需要 N 个集合，id 数组的初始化就显而易见了即 id[i] = i 。
public class QuickFind implements IDynamicConnectivity {
private int[] id;
public QuickFind(int size) {
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
}
tips: 其实这里等式的右边半只要不重复皆可，它就是集合的唯一标识，不一定需要等于 i，如果你喜欢 id[i] = i + 114514 都是可以的。
@Override
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
Quick-Find 实现顾名思义，查询很快，他能在 O1 的时间复杂度中获取到结果，但所带来的代价就是 Union 操作的时间复杂度很慢，当我们数组元素非常多时 N 会线性增长。
public class QuickFind implements IDynamicConnectivity{
private int[] id;
public QuickFind(int size) {
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
// On的查找时间
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
@Override
// O1的比较时间
public boolean connected(int p, int q) {
return id[p] == id[q];
}
}
Quick-Union
刚刚我们了解完了 Quick-Find 实现，如果我们面对的是一个 Union 操作频繁的场景，那么 Quick-Find 就无法体现出他的优势，我们需要更新我们的模型，以提高 Union 操作的效率。我们分析在 Quick-Find 中 Union 的实现。
@Override
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
@Override
public void union(int p, int q) {
int proot = findRoot(p);
int qroot = findRoot(q);
id[proot] = qroot;
}
复杂度分析
空间复杂度：由于需要 N 个空间存储每个节点所在的集合，所以空间复杂度就是 On
时间复杂度分析如下
Init
Union
Find
N
最快O1 最差On
最快O1 最差On
Init：初始化的时候需要遍历一遍数组，所以时间复杂度是 On
Union & Find：从代码可知，这两个方法的实现都关联到 findRoot 方法的时间复杂度。而findRoot 方法时间复杂度是不稳定的。他的时间复杂度，与节点距离根节点的高度有关。当每个节点都是根节点的时候，findRoot 方法的时间复杂度就是 O1，当所有节点都在同一棵树上，并且这个树退化成了链表，那么此时时间复杂度就是 On。
On 是怎么诞生的？我们现在有 5 个节点，那么当我们union(0,1)的时候他会形成一个2层的树，但我们继续 union(0,2) 的时候就会形成一个3层的树，依次类推，N 个节点最终会形成一个 N 层的树，此时树退化成了链表。
总结
Quick-Union 实现是为了能提高我们合并两个集合的效率，把节点存储在树结构上，可以使得查询只需要访问一条路径上的节点，减少了访问无关节点的访问。虽然 Union & Find 的时间复杂度都是最差 On，看起来好像没有 Quick-Find 实现来的稳定高效，但如果是出现在一个 Union 操作频繁的场景，他带来的收益是客观的。虽然我们提出了一个不稳定的实现，但我们得到了个更高效的模型。
public class QuickUnion implements IDynamicConnectivity{
private int[] id;
public QuickUnion(int size) {
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
public void union(int p, int q) {
int proot = findRoot(p);
int qroot = findRoot(q);
id[proot] = qroot;
}
@Override
public boolean connected(int p, int q) {
return findRoot(p) == findRoot(q);
}
// 最坏 On 的查找时间
private int findRoot(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}
}
Weighted Quick-Union
在刚刚我们一起实现完 Quick-Union 后，得到了一个不稳定的最差时间复杂度为 On 的 Union & Find 实现，我们知道影响这个时间复杂度的核心原因是树的层数，很快我们就能想到优化数的层数，以达到优化找寻到根节点的时间复杂度。
干掉On
在 Quick-Union 的形成 On 的原因其实很好理解，聪明的你也肯定想到了解决的办法。那就是反过。让那个独立的树合并进大的树。这样即使合并完所有的节点，树的层数也是2层，当我们只有 5 个节点的时候不明显，但是如果 N = 1000000 呢？原先的 Quick-Union 需要 1000000 次向上查找才能查找到根节点，而这种方式，只需要 2 次，优化效果显著。
public class WeightedQuickUnion implements IDynamicConnectivity {
private int[] id;
private int[] sz;
public WeightedQuickUnion(int size) {
id = new int[size];
sz = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
sz[i] = 1;
}
}
}
@Override
public void union(int p, int q) {
int proot = findRoot(p);
int qroot = findRoot(q);
if (sz[proot] < sz[qroot]) {
id[proot] = qroot;
sz[qroot] += sz[proot];
} else {
id[qroot] = proot;
sz[proot] += sz[qroot];
}
}
Find & findRoot： 没有变化。
@Override
public boolean connected(int p, int q) {
return findRoot(p) == findRoot(q);
}
private int findRoot(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}
复杂度分析
空间复杂度：由于需要 N 个空间存储每个节点所在的集合，所以空间复杂度就是 On
时间复杂度分析如下
Init
Union
Find
N
最快O1 最差OlgN
最快O1 最差OlgN
Init：初始化的时候需要遍历一遍数组，所以时间复杂度是 On
Find & Union：和 Quick-Union 一样，Find & Union 的时间复杂是由 findRoot 方法决定的，确切来说是由树的层数决定的。在我们优化后的 Union 实现，他只会在一种情况下出现树的层数变大，那就是两个根节点的层数相同，小根节点成为大根节点叶子节点，而导致大根节点的层数增加。
那么节点的层数怎么计算？我们不难发现，我们可以粗浅的认为，但出现节点层数增加的时候，大根节点所包含的节点数量是翻倍的。我们假设有 N 个节点，我们通过 Union 操作使得所有的节点合并成了一个树，那么他最多发生 x 次翻倍，也就是 2^x = N，得到 x = lgN ，而翻倍一次层数+1，可以粗浅的认为这棵树最多有 x = lgN 层。所以 findRoot 的时间复杂度为 lgN。
