Aka: union-find
Aka union-find or merge-find. It contains a collection of non-overlapping sets.
Pros | Cons |
---|---|
Fast for finding if something is connected to another element | Provides limited operations |
Not built-in |
class DisjointSet():
class Node():
def __init__(self, value: int):
self.value = value
self.parent = self
self.size = 1
def __init__(self):
self.seen_values = set()def make_set(self, value):
if value not in self.seen_values:
node = Node(value)
self.sets.append(node)# optimized find which does path splitting to update parents during find
def find(self, node):
while node.parent != node:
node, node.parent = node.parent. node.parent.parent
return nodedef union(self, node1, node2):
node1_rep = self.find(node1)
node2_rep = self.find(node2)if node1_rep == node2_rep:
return # both are in the same set# we want the node1_rep's size to be >= node2_rep
if node1_rep.size < node2_rep.size:
node1_rep, node2_rep = node2_rep, node1_repnode2_rep.parent = node1_rep
node1_rep.size += node2_rep.size
Operations | Worst | Average |
---|---|---|
Insert (new set) | O(1) | O(1) |
Merge | O(α(n)) | O(α(n)) |
Search | O(α(n)) | O(α(n)) |
Space | O(n) | O(n) |