-
Notifications
You must be signed in to change notification settings - Fork 66
Expand file tree
/
Copy pathdisjoint_sets_forest.py
More file actions
49 lines (42 loc) · 1022 Bytes
/
disjoint_sets_forest.py
File metadata and controls
49 lines (42 loc) · 1022 Bytes
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
#!/usr/bin/env python
class node:
def __init__(self, key):
self.key = key
# key.index = self
self.p = self
self.rank = 0
self.child = []
def union(self, y):
self.find_set().link(y.find_set())
def link(self, y):
x = self
if x.rank > y.rank:
x.child.append(y)
y.p = x
else:
y.child.append(x)
x.p = y
if x.rank == y.rank:
y.rank = y.rank + 1
def find_set(self):
y = self
x = self
while y != y.p:
y = y.p
while x != x.p:
z = x
x = x.p
z.p = y
# print( y.key)
return y
def print_set(self):
x = self
while x != x.p:
x = x.p
x.print_set_aux()
def print_set_aux(self):
print(self.key)
if len(self.child) == 0:
return
for child in self.child:
child.print_set_aux()