Skip to content

zerohertzLib.algorithm.collections

Classes:

Name Description
DisjointSet

Vanilla disjoint set
DisjointSetRank

Disjoint set (union by rank)
DisjointSetSize

Disjoint set (union by size)

DisjointSet 

DisjointSet(size: int, compression: bool = False)

Vanilla disjoint set

Note

Time Complexity:

  • Without path compression:
    • Worst: \(O(V)\)
    • Average: \(O(V)\)

  • With path compression:

    • Worst: \(O(\log{V})\)
    • Average: \(O(\alpha(V))\)

  • \(V\): Node의 수

  • \(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:

Name Type Description Default
size int

Node의 수

 required
compression bool

Path compression 여부

 False

Attributes:

Name Type Description
parent

Node에 따른 부모 node의 index

Examples:

>>> disjointset = zz.algorithm.DisjointSet(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset = zz.algorithm.DisjointSet(5, True)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]

Methods:

Name Description
find

목표 node에 대한 root node 탐색
union

두 node 연결
Source code in zerohertzLib/algorithm/collections.py 
43
44
45
def __init__(self, size: int, compression: bool = False) -> None:
    self.parent = list(range(size))
    self.compression = compression

compression instance-attribute 

compression = compression

parent instance-attribute 

parent = list(range(size))

find 

find(node: int) -> int

목표 node에 대한 root node 탐색

Parameters:

Name Type Description Default
node int

목표 node의 index

 required

Returns:

Type Description
int

목표 node에 대한 root node의 index
Source code in zerohertzLib/algorithm/collections.py 
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def find(self, node: int) -> int:
    """목표 node에 대한 root node 탐색

    Args:
        node: 목표 node의 index

    Returns:
        목표 node에 대한 root node의 index
    """
    if not self.compression:
        while node != self.parent[node]:
            node = self.parent[node]
        return node
    if node != self.parent[node]:
        self.parent[node] = self.find(self.parent[node])
    return self.parent[node]

union 

union(node1: int, node2: int) -> None

두 node 연결

Parameters:

Name Type Description Default
node1 int

목표 node의 index

 required
node2 int

목표 node의 index

 required

Returns:

Type Description
None

self.parent 에 root node의 index update
Source code in zerohertzLib/algorithm/collections.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
def union(self, node1: int, node2: int) -> None:
    """두 node 연결

    Args:
        node1: 목표 node의 index
        node2: 목표 node의 index

    Returns:
        `self.parent` 에 root node의 index update
    """
    root1, root2 = self.find(node1), self.find(node2)
    if root1 != root2:
        self.parent[root2] = root1

DisjointSetRank 

DisjointSetRank(size: int)

Bases: DisjointSet

Disjoint set (union by rank)

Note

Time Complexity:

  • Worst: \(O(\log{V})\)

  • Average: \(O(\alpha(V))\)

  • \(V\): Node의 수

  • \(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:

Name Type Description Default
size int

Node의 수

 required

Attributes:

Name Type Description
parent

Node에 따른 부모 node의 index
rank

Node에 따른 rank

Examples:

>>> disjointset = zz.algorithm.DisjointSetRank(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset.rank
[2, 0, 1, 0, 0]

Methods:

Name Description
union

두 node 연결
Source code in zerohertzLib/algorithm/collections.py 
109
110
111
def __init__(self, size: int) -> None:
    super().__init__(size, True)
    self.rank = [0 for _ in range(size)]

rank instance-attribute 

rank = [0 for _ in (range(size))]

union 

union(node1: int, node2: int) -> None

두 node 연결

Parameters:

Name Type Description Default
node1 int

목표 node의 index

 required
node2 int

목표 node의 index

 required

Returns:

Type Description
None

self.parent 에 root node의 index update
Source code in zerohertzLib/algorithm/collections.py 
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
def union(self, node1: int, node2: int) -> None:
    """두 node 연결

    Args:
        node1: 목표 node의 index
        node2: 목표 node의 index

    Returns:
        `self.parent` 에 root node의 index update
    """
    root1, root2 = self.find(node1), self.find(node2)
    if root1 != root2:
        if self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        elif self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1

DisjointSetSize 

DisjointSetSize(size: int)

Bases: DisjointSet

Disjoint set (union by size)

Note

Time Complexity:

  • Worst: \(O(\log{V})\)

  • Average: \(O(\alpha(V))\)

  • \(V\): Node의 수

  • \(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:

Name Type Description Default
size int

Node의 수

 required

Attributes:

Name Type Description
parent

Node에 따른 부모 node의 index
size

Node에 따른 size

Examples:

>>> disjointset = zz.algorithm.DisjointSetSize(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset.size
[4, 1, 2, 1, 1]
>>> [disjointset.size[disjointset.find(i)] for i in range(5)]
[4, 4, 4, 4, 1]

Methods:

Name Description
union

두 node 연결
Source code in zerohertzLib/algorithm/collections.py 
166
167
168
def __init__(self, size: int) -> None:
    super().__init__(size, True)
    self.size = [1 for _ in range(size)]

size instance-attribute 

size = [1 for _ in (range(size))]

union 

union(node1: int, node2: int) -> None

두 node 연결

Parameters:

Name Type Description Default
node1 int

목표 node의 index

 required
node2 int

목표 node의 index

 required

Returns:

Type Description
None

self.parent 에 root node의 index update
Source code in zerohertzLib/algorithm/collections.py 
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
def union(self, node1: int, node2: int) -> None:
    """두 node 연결

    Args:
        node1: 목표 node의 index
        node2: 목표 node의 index

    Returns:
        `self.parent` 에 root node의 index update
    """
    root1, root2 = self.find(node1), self.find(node2)
    if self.size[root1] < self.size[root2]:
        self.parent[root1] = root2
        self.size[root2] += self.size[root1]
    else:
        self.parent[root2] = root1
        self.size[root1] += self.size[root2]