并查集

发表于   |   更新于 | 分类于

1.并查集概念

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

2. 实现方法

2.1 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class UF:
    def __init__(self):
        self.parents = []
        self.ranks = []
        pass

    def find(self, x):
        pass

    def is_connected(self, x, y):
        pass

    def union(self, x, y):
        pass

2.2 具体实现

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
class UF:
    def __init__(self):
        self.parents = []
        self.ranks = []

    def find(self, x):
        # 尾递归
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)

        # 加入ranks 防止树过高
        rank_x = self.ranks[parent_x]
        rank_y = self.ranks[parent_y]

        if rank_x == rank_y:
            self.parents[parent_y] = parent_x
            self.ranks[parent_x] += 1
        elif rank_x > rank_y:
            self.parents[parent_y] = parent_x
        else:
            self.parents[parent_x] = parent_y

2.3 Todo

Donate comment here