forked from JimChengLin/JimCollection
-
Notifications
You must be signed in to change notification settings - Fork 0
/
DisjointSet.py
78 lines (59 loc) · 1.82 KB
/
DisjointSet.py
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class DisjointSetNode:
def __init__(self, identifier, parent=None):
self.identifier = identifier
if not parent:
self.parent = self
def __repr__(self):
return self.identifier
class SetPathCompressed(DisjointSetNode):
def find(self):
cursor = self
prev_cursors = []
while cursor.parent is not cursor:
cursor = cursor.parent
prev_cursors.append(cursor)
for i in prev_cursors:
i.parent = cursor
return cursor
def union(self, other):
other.parent = self
return self
class SetUnionRank(DisjointSetNode):
def __init__(self, identifier, parent=None):
super().__init__(identifier, parent)
self.rank = 0
def find(self):
cursor = self
while cursor.parent is not cursor:
cursor = cursor.parent
return cursor
def union(self, other):
if self.rank == other.rank:
other.parent = self
return self
if self.rank < other.rank:
small, big = self, other
else:
small, big = other, self
small.parent = big
return big
if __name__ == '__main__':
sample_1 = ('c', 'h', 'e', 'b')
sample_2 = ('f', 'd', 'g')
sample_1 = [SetUnionRank(i) for i in sample_1]
sample_2 = [SetUnionRank(i) for i in sample_2]
for i in sample_1[1:]:
sample_1[0].union(i)
for i in sample_2[1:]:
sample_2[0].union(i)
for i in sample_1:
if i.find() is not sample_1[0]:
raise Exception
for i in sample_2:
if i.find() is not sample_2[0]:
raise Exception
sample_1[0].union(sample_2[0])
for i in sample_1[1:] + sample_2:
print(i.find())
if i.find() is not sample_1[0]:
raise Exception