python union find
class DisjointSet:
def __init__(self, n):
self.data = list(range(n))
self.size = n
def find(self, index):
return self.data[index]
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y:
return
for i in range(self.size):
if self.find(i) == y:
self.data[i] = x
@property
def length(self):
return len(set(self.data))
disjoint = DisjointSet(10)
disjoint.union(0, 1)
disjoint.union(1, 2)
disjoint.union(2, 3)
disjoint.union(4, 5)
disjoint.union(5, 6)
disjoint.union(6, 7)
disjoint.union(8, 9)
print(disjoint.data)
print(disjoint.length)
# [0, 0, 0, 0, 4, 4, 4, 4, 8, 8]
# 3