FilesExpand file tree

 master

/

disjointset.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (56 loc) · 1.66 KB

 master

/

disjointset.py

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (56 loc) · 1.66 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# disjoint sets

# https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java

class Node(object):

def __init__(self, data, parent = None, rank = 0):

self.data = data

self.parent = parent

self.rank = rank

def __str__(self):

return str(self.data)

def __repr__(self):

return self.__str__()

class DisjointSet(object):

def __init__(self):

self.map = {}

def make_set(self, data):

node = Node(data)

node.parent = node

self.map[data] = node

def union(self, data1, data2):

node1 = self.map[data1]

node2 = self.map[data2]

parent1 = self.find_set_util(node1)

parent2 = self.find_set_util(node2)

if parent1.data == parent2.data:

return

if parent1.rank >= parent2.rank:

if parent1.rank == parent2.rank:

parent1.rank = parent1.rank + 1

parent2.parent = parent1

else:

parent1.parent = parent2

def find_set(self, data):

return self.find_set_util(self.map[data])

def find_set_util(self, node):

parent = node.parent

if parent == node:

return parent

node.parent = self.find_set_util(node.parent)

return node.parent

if __name__ == '__main__':

ds = DisjointSet()

ds.make_set(1)

ds.make_set(2)

ds.make_set(3)

ds.make_set(4)

ds.make_set(5)

ds.make_set(6)

ds.make_set(7)

ds.union(1,2)

ds.union(2,3)

ds.union(4,5)

ds.union(6,7)

ds.union(5,6)

ds.union(3,7)

for i in range(1,8):

print(ds.find_set(i))