「并查集」专题 7：并查集第 6 版 quick-union 基于路径压缩的递归实现
重点提示：这一节重要。
代码的实现的理解有一些绕。这一版我们实现压缩更彻底的路径压缩。其实我们不看上面的分析，我们想象路径压缩的目的是什么，就是让我们的并查集表示的树结构层数更低，那么最优的情况应该是下面这样，把一棵树压缩成 $2$ 层，所有的结点都指向一个根，这才是把一个并查集压缩到最彻底的情况。
那么，代码又应该如何实现呢？我们需要使用递归的思想。这一版代码的实现难点就在于：应该定义 find(p) 返回的是 p 这个结点的父结点。
Java 代码：
/**
* 返回索引为 p 的元素的根结点
* 理解这个方法的关键点：我们就是要把这个结点的父结点指向根结点，
* 既然父亲结点不是根结点，我们就继续拿父亲结点找根结点
* 一致递归找下去，
* 最后返回的时候，写 parent[p] 是可以的
* 写 parent[parent[p]] 也是没有问题的
*
* @param p
* @return
*/
public int find(int p) {
// 在 find 的时候执行路径压缩
assert p >= 0 && p < count;
// 注意：这里是 if 不是 while，否则就变成循环
if (p != parent[p]) {
// 这一行代码的逻辑要想想清楚
// 只要不是根结点
// 就把父亲结点指向父亲结点的父亲结点
parent[p] = find(parent[p]);
}
return parent[p];
}最后，我们来比较一下基于路径压缩的两种方法。
并查集能够很好地帮助我们解决网络中两个结点是否连接的问题。但是，对于网络中的两个结点的路径，最短路径的问题，我们就要使用图来解决。
关于路径压缩的思考
写到这里，我们发现在路径压缩的过程中，我们之前引入的辅助合并的数组，不管是 rank 还是 size，它们的定义都不准确了，因为我们在路径压缩的过程中没有对它们的定义进行维护。这一点其实并不影响我们的算法的正确性，我们不去维护 rank 数组和 size 数组的定义，是因为第 1 点：难于实现，第 2 点： rank 数组还是 size 数组的当前实现仍然可以作为一个参考值，比起随机的做法要更有意义一些。
其实写到这里，数组 rank 还是数组 size 的意义都不太重要了，我们只须要在 find 的时候，做好路径压缩，把孩子结点指向父亲结点即可。
