В граф добавляются рёбра, и в любой момент спрашивают: в одной ли компоненте a и b? Запускать BFS/DFS каждый раз — O(V + E). Union-Find (Disjoint Set Union, DSU) хранит компоненты как множества и отвечает на этот вопрос почти за O(1).
Идея: лес
Каждое множество — это дерево, а корень дерева — представитель множества. Лес лежит в одном массиве: parent[i] — родитель i, а при parent[r] == r вершина r — корень. find(x) идёт до корня, union(a, b) подвешивает один корень под другой.
Если всегда подвешивать одну и ту же сторону, дерево вырождается в цепочку и find становится O(n). Ниже разница на 1000 последовательных объединениях.
def depth(parent, x):
d = 0
while parent[x] != x:
x, d = parent[x], d + 1
return d
def find(parent, x):
while parent[x] != x:
x = parent[x]
return x
n = 1000
naive = list(range(n))
by_size, size = list(range(n)), [1] * n
for i in range(n - 1):
naive[find(naive, i)] = find(naive, i + 1) # always hang the left root
a, b = find(by_size, i), find(by_size, i + 1)
if size[a] < size[b]:
a, b = b, a
by_size[b] = a # small tree under the large
size[a] += size[b]