高手都爱用的算法：并查集（下）

上篇提出一个问题，合并操作时，到底选A还是B当合并后的根呢？
我们来看下Union(1, 5)，两种选择导致的结果：

并查集.001.jpeg

现在试着查找4的根，方案1中，需要寻找两次；方案2中，就需要寻找3次；
在一些极端情况下，最后的树可能是这样的：

并查集.002.jpeg

两种合并策略

可见，如果不作平衡，会导致合并操作的速度越来越慢（因为Union依赖find操作），因此，也有两个策略来获得平衡：

1. 按大小合并
   在上面的例子中，比较1和5这两棵树的子节点数量，也就看谁家人多，人多的自然当老大，例子中1有两个子节点，而5孤家寡人一个，就只好屈居人下了。
2. 按树的高度合并
   树的高度是指一棵树从根到叶子的最大边数量，也就是遍历子节点的最大深度，这里也是1比5要高，所以结果也是1当老大。

路径压缩

做到这一步，合并操作几乎无缺点了，但是还是避免不了最坏情况的发生，图中的4始终查找次数都是2，这要是在几千万的数量级中，浪费运算时间就无法忽视了，这时我们想到，find(4)的结果始终是它祖父1，不如直接就挂到1下，给1直接当儿子算了（这辈分太乱了😓），这样所有的子节点都直接挂到根下，这个过程被称为“路径压缩”：

并查集.003.jpeg

然而，做过路径压缩的树由于高度保持为1，对“按树的高度合并”造成了困扰，为了保持算法能继续进行，我们可以保留“曾经最大高度”，也就是说，我们干脆不去计算“路径压缩”后的树高度了，还拿这个“过去的值”来比大小。

完整的Swift实现

class Solution {
    var pre:[Int]
    init() {
        self.pre = [Int]()
    }
    func findCircleNum(_ M: [[Int]]) -> Int {
        
        if (M.count > 0) {
            self.pre = [Int](repeating: -1, count: M.count)
            for i in 0...M.count - 1 {
                if (M[i].count == M.count) {
                    for j in 0...M[i].count - 1 {
                        if (M[i][j] == 1) {
                            union(i, j)
                        }
                    }
                } else {
                    return 0 //异常数据
                }
            }
            var count = 0
            for (i, v) in pre.enumerated() {
                if (v == -1) {
                    count+=1
                }
            }
            return count
        }
        return 0
    }
    
    func union( _ i:Int, _ j:Int) {
        let preI = findSet(i)
        let preJ = findSet(j)
        if (preI != preJ) {
            self.pre[preI] = preJ
        }
    }
    func findSet(_ i:Int)->Int {
        var root = i
        while (self.pre[root] != -1) {
            root = self.pre[root]
        }
//        var tempI = i
//        // 路径压缩
//        while (self.pre[tempI] != -1) {
//            var pre = self.pre[tempI];
//            self.pre[tempI] = root
//            tempI = pre
//        }
        return root
    }
}

实际运行时间对比