return parent node.parent = self.find_set(parent) # path compression in line above: once parent is found, each nodes' # parent pointer gets changed to the "highest rank node" # or "representative" of the set return node.parent class DisjointSet: # Tree def __init__(self): self.map = {} # key, value = data, node def make_set(self, data): node = Node(data) self.map[data] = node def union_by_rank(self, data1, data2): """ Combines two sets together to one. Does union by rank return true if data1 and data2 are in different set before union else false. """ n1, n2 = self.map[data1], self.map[data2] parent1, parent2 = self.find_set(n1), self.find_set(n2) if(parent1.data == parent2.data): return False if (parent1.rank >= parent2.rank): parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank parent2.parent = parent1 else: parent1.parent = parent2 return True def find_set(self, data): """ Finds the representative of this set """ node = self.map[data] return node._find_set() 32:["$33"] 31:["$32"] 35:T439,

O(n \cdot \alpha (n))

Disjoint Set / Union Find