52 | 理论讲解：并查集

并查集 (union & find) 是一种树型的数据结构，⽤于处理⼀些不交集(Disjoint Sets)的合并及查询问题。

Find:确定元素属于哪一个⼦集。它可以被用来确定两个元素是否属于同一⼦集。

Union:将两个⼦集合并成同⼀个集合。

直观表示：

数据结构：

伪代码：
最后的 xRoot.parent = yRoot，也可改为yRoot.parent = xRoot，因为目的只是为了合并

在生活中的例子

通过小弟找⽼大
帮派识别

两种优化方式

按秩合并：wiki
合并时将元素所在深度小的集合合并到元素所在深度大的集合。

伪代码：

路径压缩：wiki
找到最久远的祖先时“顺便”把它的子孙直接连接到它上面

java 代码：

class QuickUnionUF(N: Int) {
    val parent = IntArray(N) { it }
    var count=N

    fun findRoot(p: Int): Int {
        var root = p
        while (root != parent[root]) {
            root = parent[root]
        }
        //路径压缩
        var r = p
        while (r != parent[r]) {
            r = parent[r].also {
                parent[r] = root
            }
        }
        return root
    }

    fun connected(p: Int, q: Int): Boolean {
        return findRoot(p) == findRoot(q)
    }

    fun union(p: Int, q: Int) {
        val qRoot = findRoot(q)
        val pRoot = findRoot(p)
        //任选一句均可
        parent[qRoot] = pRoot
      //roots[pRoot]=qRoot
        count--
    }

}