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
