程序员的玩具

LeetCode刷题笔记——UnionFind

并查集介绍

首先接触到并查集，是通过本科的数据结构课本《数据结构、算法与应用——C++语言描述》。课本中在三个比较偏僻的角落，分别引出了等价类的概念、离线等价类问题和在线等价类问题。在第一处，课本给出了等价类的定义：等价类是指其中的元素具有等价关系的集合，而等价关系是指一类满足反身性、对称性和传递性的二元关系。然后明确了在线等价类问题和离线等价类问题各自的定义。最后分别使用数组和模拟指针两种方法对定长的在线等价类问题给出了初步解决方案。第二处对离线等价类问题进行了解决，第三处对在线等价类问题进行了解决。

python伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class UnionFind():
    def __init__(self, length):
        self.length = length
        self.components = length
        self.pre = [i for i in range(length)]

    def root(self, i):
        # find root
        length = 0
        c = i
        while self.pre[i] != i:
            i = self.pre[i]
            length += 1
        root = i

        # path compress
        temp = self.pre[c]
        while temp != c:
            self.pre[c] = root
            c = temp
            temp = self.pre[c]
        return root

    def isConnect(self, i, j):
        return self.root(i) == self.root(j)

    def add(self, i, j):
        root_i, root_j = self.root(i), self.root(j)
        if root_i != root_j:
            self.pre[root_i] = root_j
            self.components -= 1

    def componentsNum(self):
        return self.components

547. Friend Circles

并查集基本思路，没啥。

200. Number of Islands

这道题之前用DFS做过一遍，结果这次用了并查集效率更慢了，就是遍历每对相邻节点的边。

128. Longest Consecutive Sequence

之前的并查集是使用模拟指针做的，直接用元素的值作为键，这样的话就要求元素的值必须连续。因为通过模拟指针维护的并查集内部存储的是两个数组data和parent，数组分别维护元素的索引以及元素父节点的索引。这样的话，如果元素是不连续的，比如维护[1,2,100,200]这几个元素的等价关系，就需要数组的长度为200。解决的个问题可以使用间接寻址法，只维护长度为四的data，data中存放带有指针的node对象，并且维护一个字典，字典维护元素索引到data下标的映射。
使用基于链表的方法实现并查集并基于此解决该问题。思路是遍历列表，在并查集中加入以列表中的值为索引的节点，并检查与该元素相邻的元素是否在并查集中，如果在，就进行union操作。遍历一遍链表并建好并查集就可以得到最大的连续串了。
然而solution中给出了一个直接的算法，仅使用一个set就可以，遍历列表，找到每一个连续串的最左端，然后不断递增元素的值并检查是否存在在集合之中。运行的时间差不多在我的基于并查集的时间的一半。按理说并查集中已经实现了基于重量的合并规则以及路径压缩技巧，总的union和find操作几乎平摊下来是线性时间。那么为什么效率还这么低呢？我捉摸着应该是因为官方的基于集合的方法是解决的离线等价类的问题，而我的并查集方法解决的是在线等价类问题。举个栗子，在运行一次之后，在原有列表上又加了两个元素并且再次判断最长的连续串，前者还需要遍历列表，而我的方法只需要常数时间就可以给出答案。

959. Regions Cut By Slashes

Solution中给出的答案是将每一个grid分成4份，等于是做出一个长度为4*N*N的UnionFind，然后对其中一定连接的部分先连上，然后再根据grid中的符号对并查集进行连接。我的做法稍稍有一点不同，就是将必定相连的部分默认连接，因此只需要一个长度为N*N*2+N*2的并查集就可以，不过这样一来代码就复杂一些，因为对每个小形状的编号就没第一种方法简单了。总的方法的复杂度是O(N*N*alpha(N))，其中alpha是反阿克曼函数，这个函数我也不太懂，只知道是一个增长的十分慢的函数，可以看做是常数函数，按秩合并和路径压缩的并查集的时间复杂度就是alpha(N)。

399. Evaluate Division

这道题我的思路是利用链指针实现的并查集，判断两个元素能否计算（是否连通），可以连通的话，找到两个元素的共同根节点以及到根节点的路径，然后使用另外字典记录下路径中每一步的值，将路径的每一步的值相乘就得到整条计算路径的值。由于需要记录路径的值，这里就把路径压缩取消了。看提交中，别人使用的更多的是基于图的方法，就是对给定的equation列表建边，然后在求解的时候使用bfs探索是否存在路径以及最短的路径是什么，然后对路径中的每一步相乘即可。比较两者，我的不带路径压缩的指针并查集实际上也是构建了一张图，但是这张图实际上是一棵树，因此任意两点的路径是唯一的，而且树的形状与参数顺序有关。这使得可能在树中对于某些边不予存储，这在求解计算路径时得到的路径可能会比建图的方法长很多。但好在并查集可以以常数时间判断两个节点之间是否有路径，这个是图的方法没有的。实际上可能可以将二者结合？

参考

并查集(Union-Find)算法介绍

本站总访问量次