并查集原理及联通分量个数问题

Posted on

并查集原理及联通分量个数问题

[TOC]

一、并查集

并查集是一个复杂的数据结构。在lc中大概有30道题左右（官方给出）

集合运算

常见的集合运算有：

交、并、补、差、判定一个元素是否属于某一集合

并查集： 集合并、查某元素属于什么集合

存储实现

使用树结构表示集合，树的每个结点代表一个集合元素

图示

image-20200513205634171

如图所示有两个集合，如何判定A-I九个元素属于哪个集合？

例：E 和 C是否为同一个集合。

可以不停的向上查找元素的父节点。判断是否有同一个根节点：

E->B->A

C->A

可见 E和C是同一集合

实际刷题中往往会给一个关系矩阵, 需要自己创建所有集合。

初始化每个元素为一个集合：

image-20200513210537820

有九个集合，通过关系矩阵在集合进行并操作：

例： 在关系矩阵中，A和B在同一集合。则将{A}和{B}并起来。即B指向A。

image-20200513211007745

最终构造出由关系矩阵得到的并查集

抽象数据

元素类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node(object):
    def __init__(self, data, parent=None):
        self.data = data
        self.parent = parent
        
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0

    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data] = node
        self.num_sets += 1
    
    def union(self, data1, data2):
        pass
    
    def find(self, data):
        pass

优化

随着树的高度的增加，find方法进行查询的时候，随着大量的union操作调用，导致复杂度的线性上升。导致树结构变成一个类似于线性表的结构。这种变化叫做树的退化，并查集算法需要对此问题进行优化。

定义Rank

对于每棵树，记录树的高度Rank，当进行union操作，合并两棵树时，如果其Rank不同，那么由Rank小树的连向Rank大的树。

image-20200513212325663

上图中左边的树Rank=3，右边的树Rank=2，Rank小的连向Rank大的。

路径压缩

image-20200513212846766

上图中C的根节点是A，可以直接将C指向A，进行路径压缩操作。

优化后的代码实现

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
35
36
37
class Node(object):
    def __init__(self, data, parent=None, rank=0):
        self.data = data
        self.parent = parent
        self.rank = rank
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0
    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data]=node
        self.num_sets+=1
    def find(self, data):
        node = self.map[data]
        r = node
        while r!= r.parent:
            r = r.parent
        k = node
        while k!=r:
            j = k.parent
            k.parent = r
            k = j
        return r
    def union(self, data1, data2):
        parent1 = self.find(data1)
        parent2 = self.find(data2)
        if parent1.data == parent2.data:
            return
        if parent1.rank >= parent2.rank:
            if parent1.rank == parent2.rank:
                parent1.rank+=1
            parent2.parent = parent1
        else:
            parent1.parent = parent2
        self.num_sets -=1

LC #547

LeetCode第547题的答案就出来了：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
class Node(object):
    def __init__(self, data, parent=None, rank=0):
        self.data = data
        self.parent = parent
        self.rank = rank
class DisjointSet(object):
    def __init__(self):
        self.map = {}
        self.num_sets = 0
    def make_set(self, data):
        node = Node(data)
        node.parent = node
        self.map[data]=node
        self.num_sets+=1
    def find(self, data):
        node = self.map[data]
        r = node
        while r!= r.parent:
            r = r.parent
        k = node
        while k!=r:
            j = k.parent
            k.parent = r
            k = j
        return r
    def union(self, data1, data2):
        parent1 = self.find(data1)
        parent2 = self.find(data2)
        if parent1.data == parent2.data:
            return
        if parent1.rank >= parent2.rank:
            if parent1.rank == parent2.rank:
                parent1.rank+=1
            parent2.parent = parent1
        else:
            parent1.parent = parent2
        self.num_sets -=1
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        ds = DisjointSet()
        for i in range(len(M)):
            ds.make_set(i)
        for i in range(len(M)):
            for j in range(i+1, len(M)):
                if M[i][j] == 1:
                    ds.union(i, j)
        return ds.num_sets