I woke up, checked email inbox and Slack, and realized today is a US holiday.
std::vector<bool> is specializedclass UnionFind:
def __init__(self, n: int):
# parent[i] = parent of i (if parent[i] == i, i is a root)
self.parent = list(range(n))
# size[i] = size of the set whose root is i (only valid for roots)
self.size = [1] * n
def find(self, x: int) -> int:
# Find root with path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a: int, b: int) -> bool:
# Union sets containing a and b
ra = self.find(a)
rb = self.find(b)
if ra == rb:
return False # already in same set
# Union by size (attach smaller under larger)
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def same(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
def component_size(self, x: int) -> int:
return self.size[self.find(x)]TODO: