Disjoint-set

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
Implementations
Python: Custom implementation

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 node

def 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_rep

node2_rep.parent = node1_rep
node1_rep.size += node2_rep.size

Operations Worst Average
Insert (new set)O(1)O(1)
MergeO(α(n))O(α(n))
SearchO(α(n))O(α(n))
SpaceO(n)O(n)
LeetCode Problems
Number of Islands
Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands.


Similar