并查集

并查集是一种树形的数据结构，用于处理一些不交集（不相交的两个集合）的合并及查询问题。

它支持两种操作：

1. 查找：确定某个元素处于哪个子集。

2. 合并：将两个子集合并成一个集合。

思想

新学期学校组织春游，要求每个人必须和同班同学结伴游玩。因为是新生大家都还不熟悉，无法确认对方是否是自己同学，因此只能询问对方班主任姓名，来进行确认。

并查集就是在这种思想下产生的数据结构。

上例只需要查找一层就能获得想要的结果。实际情况下，往往需要往上查找好几层，才能找到想要的结果。

并查集包含了多个树形集合。每个集合的根节点被选取作为代表，用来表示整个集合。就如同班主任一样。

查找操作返回元素所属集合的代表；合并操作是对于两个集合而言的，它将某个代表设置为另一个代表的子节点。

基础操作

初始化

设置单元素集合。

func makeSet(x int) {
    fa[x] = x
    return
}

查找

查找某个元素的祖先。

func find(x int) int {
    if fa[x] == x { // 如果是祖先则返回
        return x
    }
    return find(fa[x]) // 如果自己不是祖先，则问上级祖先是谁
}

合并

只需要将一个集合设置为另一个集合的子节点，就能实现合并。

func union(x, y) {
    xRoot := find(x)
    yRoot := find(y)
    if xRoot == yRoot {
        return
    }
    fa[xRoot] = yRoot
}

优化方法

路径压缩

每次进行查找操作，都需要一层一层往上询问，效率比较低。

所谓“路径压缩”，就是在进行“查找”时，将路径上的每个节点直接连到根节点，使得树更加扁平化。

“路径压缩”可以使以后的”查找“操作更加快速。

func find(x int) int {
    if fa[x] != x {
        fa[x] = find(fa[x])
    }
    return fa[x]
}

按秩合并（启发式合并）

在进行合并操作时，无论将哪一个集合连接到另一个集合下面，总能得到正确的结果。但是采用不同的连接方法，对于查找操作，将会存在不同的时间复杂度。

将一颗节点数和深度都较小的集合树连接到另一颗集合树下，相比于另一种方案，执行查找操作的用时会更少。

但是不可能总能得到节点数和深度都较小的集合树，因此可以选择两者之一作为衡量指标。

现在讨论使用深度作为衡量指标。节点数的讨论类似。

路径压缩会改变树的高度，如果使用深度作为衡量指标，每次压缩时都要重新计算树的深度，查找算法复杂度会变高。初始化集合时，可以使用”秩“代替”深度“。将秩初始化为0，两个秩同为r的集合树合并时，它们的秩r+1，否则秩不变。如果没有路径压缩，秩和深度则总是相等的。

func makeSet(x int) {
    fa[x] = x
    rank[x] = 0
    return
}

// ... 省略查找算法

func union(x, y) {
    xRoot := find(x)
    yRoot := find(y)
    if xRoot == yRoot {
        return
    }

    if rank[xRoot] < rank[yRoot] {
        fa[xRoot] = yRoot
    } else if rank[xRoot] > rank[yRoot] {
        fa[yRoot] = xRoot
    } else {
        fa[xRoot] = yRoot
        rank[yRoot]++
    }
}

补充

带权并查集

带权并查集的节点之间，具有一定的权重。比如一个部门中，副部长的职级高，他和部长之间联系的紧密程度，要高于普通成员和部长之间的联系，权重就比较高。此时的合并规则，既可以使用秩，又可以自己设定。