python union find

Solutions on MaxInterview for python union find by the best coders in the world

showing results for - "python union find"
Maria José
18 Jan 2019
1class DisjointSet:
2    def __init__(self, n):
3        self.data = list(range(n))
4        self.size = n
5
6    def find(self, index):
7        return self.data[index]
8
9
10	def union(self, x, y):
11    	x, y = self.find(x), self.find(y)
12
13	    if x == y:
14    	    return
15
16	    for i in range(self.size):
17    	    if self.find(i) == y:
18        	    self.data[i] = x
19
20
21    @property
22    def length(self):
23        return len(set(self.data))
24
25
26
27
28disjoint = DisjointSet(10)
29
30disjoint.union(0, 1)
31disjoint.union(1, 2)
32disjoint.union(2, 3)
33disjoint.union(4, 5)
34disjoint.union(5, 6)
35disjoint.union(6, 7)
36disjoint.union(8, 9)
37
38print(disjoint.data)
39print(disjoint.length)
40
41
42# [0, 0, 0, 0, 4, 4, 4, 4, 8, 8]
43# 3