并查集学习笔记

概念

并查集是一种基于树形结构的数据结构，用来维护一些不相交集合（Disjoint Set）。并查集支持如下操作：

makeSet(x)：创建一个新的由元素 x 独立组成的集合。
union(x, y)：将包含 x 和 y 的两个集合合并为一个集合。
find(x)：找到元素 x 所在的集合的代表元素。

实现

并查集的实现可以使用数组或者链表。我们以数组来举例说明，并查集的元素按集合划分，每个集合的代表元素是它的根节点。

假设我们要实现一个并查集，并且元素只能是整数，那么首先需要定义一个数组 parent，用来存储每个元素所在集合的根节点。初始时，每个元素都是独立的一个集合，因此每个元素的根节点都是它本身。

pythonCopy Code
parent = [i for i in range(n)]  # n 是元素的个数

然后就可以分别实现三个操作了。

makeSet(x)

创建一个新的由元素 x 独立组成的集合，这个操作非常简单，只需要将 x 的根节点设为 x 自己即可。

pythonCopy Code
def makeSet(x):
    parent[x] = x

find(x)

找到元素 x 所在的集合的代表元素，这里需要使用路径压缩来优化查找效率。路径压缩就是在执行 find(x) 操作时，将搜索路径上的每个节点都直接连接到根节点上，从而使整个树更加扁平化。

pythonCopy Code
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

union(x, y)

将包含 x 和 y 的两个集合合并为一个集合，这里也需要使用路径压缩来优化效率。具体实现时，我们可以让 x 的根节点连接到 y 的根节点上，从而将 x 所在集合的所有元素都并入到 y 所在的集合中。

pythonCopy Code
def union(x, y):
    root_x, root_y = find(x), find(y)
    if root_x != root_y:
        parent[root_x] = root_y

实例

下面举一个例子来说明如何使用并查集解决某些问题。假设有一个列表，其中包含了若干个区间，每个区间由左右端点表示。我们希望将所有相交的区间合并成一个大区间，输出最终的区间数。

例如，给定以下区间：

Copy Code
[[1, 3], [2, 6], [8, 10], [15, 18]]

其中第一个区间是 [1, 3]，表示左端点为 1，右端点为 3。我们可以通过并查集来解决这个问题。具体地，我们将每个区间看作一个节点，如果两个区间有交集，则将它们所在的集合合并成一个。

pythonCopy Code
n_intervals = len(intervals)
parent = [i for i in range(n_intervals)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x, root_y = find(x), find(y)
    if root_x != root_y:
        parent[root_x] = root_y

for i in range(n_intervals):
    for j in range(i+1, n_intervals):
        if intervals[i][1] >= intervals[j][0] and intervals[j][1] >= intervals[i][0]:
            union(i, j)

n_sets = len(set(find(i) for i in range(n_intervals)))

在上面的代码中，find(x) 函数返回 x 所在集合的代表元素，而 union(x, y) 函数将 x 和 y 所在的集合合并成一个。

最后，我们使用 set() 函数来统计有多少个不相交的集合，也就是答案。

以上就是并查集的基本操作和应用。