Объединение по рангу и оценка обратной функции Аккермана
Добавьте объединение по рангу, чтобы сохранять деревья плоскими, и разберитесь, почему совокупная оптимизация даёт амортизированное O(alpha(n)), то есть фактически константное время
«Объединение по рангу и оценка обратной функции Аккермана» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Почему деревья становятся высокими без ранга
Обычное сжатие путей предотвращает появление высоких деревьев после обходов, но во время первоначальных операций union всё ещё можно построить высокое дерево, если всегда подвешивать корень большего дерева под корень меньшего. Union по рангу решает эту проблему: он отслеживает верхнюю границу высоты дерева (ранг) и всегда подвешивает более мелкое дерево под более глубокое.
Ранг не совпадает в точности с высотой — сжатие путей может уменьшить высоту ниже ранга, — но является её верхней границей. Сохраняя более глубокое дерево новым корнем, мы гарантируем, что ранг увеличивается только при объединении деревьев с одинаковым рангом, поэтому максимальный ранг ограничен величиной O(log n).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # initially all trees have rank 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# Attach lower-rank tree under higher-rank tree
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1 # only increases when ranks are equal
return TrueТри случая union по рангу
При объединении двух компонент с корнями px и py возможны три случая в зависимости от их рангов:
- rank[px] > rank[py]: подвесить py к px — ранг px не изменяется
- rank[px] < rank[py]: подвесить px к py — ранг py не изменяется
- rank[px] == rank[py]: подвесить py к px (или наоборот) — ранг нового корня увеличивается на 1
Ранг увеличивается только в случае равных рангов. Это означает, что для ранга n требуется как минимум 2^n узлов, поэтому максимальный ранг равен O(log n). Благодаря этому пути find остаются короткими даже без сжатия путей.
# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8
def find(x):
while dsu_parent[x] != x:
x = dsu_parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return
if dsu_rank[px] < dsu_rank[py]:
px, py = py, px
dsu_parent[py] = px
if dsu_rank[px] == dsu_rank[py]:
dsu_rank[px] += 1
# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank) # max rank <= log2(8) = 3
print('Root of all:', find(0))Сочетание сжатия путей и union по рангу
Когда сжатие путей и union по рангу используются вместе, амортизированное время на операцию снижается до O(alpha(n)) — обратной функции Аккермана. Для любого практически значимого размера входных данных (до 2^65536) alpha(n) не превышает 4. Фактически это константное время.
Сжатие путей выпрямляет деревья снизу вверх после обходов, а union по рангу не даёт деревьям расти вверх во время объединений. Вместе эти методы дополняют друг друга: ранг ограничивает начальную глубину, а сжатие устраняет её после первого обхода.
class OptimalDSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # union by rank
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank)) # stays very smallПонимание обратной функции Аккермана
Функция Аккермана A(m, n) растёт чрезвычайно быстро — быстрее любой примитивно-рекурсивной функции. Её обратная функция, alpha(n), определяется как наименьшее m, для которого A(m, m) >= n. Поскольку функция Аккермана растёт настолько быстро, alpha(n) увеличивается невообразимо медленно.
Для n = 10^80 (число атомов в наблюдаемой Вселенной) alpha(n) всё ещё равна всего 4. Поэтому DSU с обеими оптимизациями во всех практических случаях считают структурой с фактически константным временем работы. Вы никогда не столкнётесь с реальной задачей, достаточно большой, чтобы alpha(n) превысила 5.
# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large
alpha_thresholds = {
1: 'n=1',
2: 'n up to 3',
3: 'n up to about 2048',
4: 'n up to 10^19728 (far beyond atoms in universe)',
5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')Ранг или размер: что выбрать
Альтернатива union по рангу — это union по размеру: всегда подвешивать дерево меньшего размера под дерево большего размера. Оба подхода гарантируют высоту O(log n). Union по размеру часто проще для понимания, поскольку размеры являются точными величинами, тогда как ранги — это верхние границы, которые после сжатия могут не отражать настоящую высоту.
На собеседованиях допустим любой из этих подходов. Union по размеру дополнительно позволяет бесплатно получать размеры компонент, что требуется во многих задачах. Union по рангу немного элегантнее с теоретической точки зрения и соответствует исходному доказательству Тарьяна оценки через обратную функцию Аккермана.
class DSUBySize:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.size[px] < self.size[py]:
px, py = py, px # always attach smaller under larger
self.parent[py] = px
self.size[px] += self.size[py]
return True
dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])Набросок доказательства: почему ранг остаётся O(log n)
Индукцией можно доказать, что дерево DSU с рангом r содержит как минимум 2^r узлов. Базовый случай: ранг 0 означает один узел (2^0 = 1). Индукционный переход: ранг r увеличивается только при объединении двух деревьев ранга r-1. По индукционному предположению каждое поддерево содержит как минимум 2^(r-1) узлов, поэтому объединённое дерево содержит как минимум 2 × 2^(r-1) = 2^r узлов.
Поскольку дерево ранга r содержит как минимум 2^r узлов, а всего у нас n узлов, максимальный ранг не превышает log₂(n). Значит, find без сжатия путей занимает O(log n), а со сжатием путей амортизированная стоимость становится значительно меньше.
# Verify the 2^rank lower bound empirically
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.rank[px] < self.rank[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]: self.rank[px] += 1
n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
if dsu.find(root) == root:
r = dsu.rank[root]
print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')Шаблон DSU для спортивного программирования
В спортивном программировании и на собеседованиях нужен проверенный на практике шаблон DSU: короткий, корректный и учитывающий все крайние случаи. В приведённом ниже шаблоне используются уполовинивание путей (однопроходное сжатие) и union по размеру — сочетание, которое легко быстро набрать и которое полностью избегает рекурсии.
Всегда инициализируйте parent[i] = i и size[i] = 1. Помните, что после find значение size корня отражает размер всей компоненты. Никогда не используйте size[x] напрямую — всегда вызывайте size[find(x)].
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.sz = [1] * n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path halving
x = self.p[x]
return x
def union(self, x, y):
x, y = self.find(x), self.find(y)
if x == y: return False
if self.sz[x] < self.sz[y]: x, y = y, x
self.p[y] = x
self.sz[x] += self.sz[y]
return True
def same(self, x, y): return self.find(x) == self.find(y)
def size(self, x): return self.sz[self.find(x)]
# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9)) # True
print(dsu.size(0)) # 3Когда DSU недостаточно
DSU поддерживает объединение множеств, но не поддерживает разделение множества обратно на два. Если задача требует и объединять, и разделять группы, нужна другая структура, например дерево связей и разрезов. DSU также не хранит элементы каждой группы напрямую — для этого потребуется дополнительный список смежности или словарь.
Кроме того, стандартный DSU без изменений не поддерживает взвешенные рёбра (взвешенный DSU — более продвинутый вариант). Для задач вроде поиска самого дешёвого пути между связанными узлами больше подходят алгоритм Дейкстры или BFS. Понимание области применимости DSU помогает не использовать его неподходящим образом.
# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces
# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)
# Example of storing group members alongside DSU
from collections import defaultdict
class DSUWithMembers:
def __init__(self, n):
self.p = list(range(n))
self.members = defaultdict(set)
for i in range(n): self.members[i].add(i)
def find(self, x):
while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
self.members[px] |= self.members[py]
del self.members[py]
self.p[py] = pxСравнение DSU с BFS/DFS для определения связности
И BFS/DFS, и DSU решают задачи статической связности, но у них разные сильные стороны. BFS/DFS работает за O(V + E) и может найти фактический путь между вершинами. DSU отвечает на множество запросов о связности для постепенно расширяющихся наборов рёбер почти за O(1) на запрос — это идеально для онлайн-алгоритмов, в которых рёбра поступают по одному.
Если все рёбра поступают заранее и вам нужна только связность, подойдёт любой из методов. Если рёбра поступают динамически и нужно отвечать на запросы о связности после добавления каждого нового ребра, DSU явно выигрывает. Для задач, где также нужен кратчайший путь, используйте BFS.
# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines
from collections import deque
def bfs_connected(graph, src, dst, n):
visited = set([src])
q = deque([src])
while q:
node = q.popleft()
if node == dst: return True
for nb in graph.get(node, []):
if nb not in visited:
visited.add(nb); q.append(nb)
return False
# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')Практика: минимальное остовное дерево с DSU
Алгоритм Крускала построения минимального остовного дерева напрямую использует DSU. Отсортируйте все рёбра по весу, затем жадно добавляйте каждое ребро, если его концы находятся в разных компонентах (цикл не образуется). DSU выполняет проверку цикла почти за O(1). Результатом будет MST из n-1 рёбер.
Это классическая демонстрация возможностей DSU: он превращает наивную проверку циклов за O(E × V) в процесс за O(E × alpha(n)). При сортировке за E log E общая временная сложность алгоритма Крускала составляет O(E log E), а операции DSU настолько быстры, что ими можно пренебречь по сравнению с сортировкой.
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
return mst_weight, mst_edges
edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w) # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)DSU с rollback: офлайн-связность
Стандартный DSU не поддерживает операции отмены. Однако DSU с rollback (также называемый DSU с историей) это позволяет: вместо сжатия путей (которое трудно отменить) используйте только union по рангу и записывайте каждую операцию union в стек. Для отката извлеките последнюю операцию с помощью pop из стека и восстановите родителя и ранг. Это позволяет решать офлайн-задачи о динамической связности, в которых рёбра могут добавляться и удаляться.
Хотя это продвинутый вариант, редко встречающийся на стандартных собеседованиях, он показывает, что union по рангу — ключевой инвариант, а не сжатие путей. Без сжатия путей каждая операция find выполняется за O(log n), а операции со стеком при rollback — за O(1), поэтому общая сложность одной операции составляет O(log n), а не O(alpha(n)).
class DSUWithRollback:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.history = [] # stack of (node, old_parent, node2, old_rank)
def find(self, x): # NO path compression (cannot undo)
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]: px, py = py, px
# Record state before modifying
self.history.append((py, self.parent[py], px, self.rank[px]))
self.parent[py] = px
if self.rank[px] == self.rank[py]: self.rank[px] += 1
return True
def rollback(self):
py, old_par_py, px, old_rank_px = self.history.pop()
self.parent[py] = old_par_py
self.rank[px] = old_rank_px
dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2)) # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2)) # FalseБыстрая проверка
Проверьте понимание концепций из курса «Структуры данных и алгоритмы — подготовка к собеседованиям по программированию», рассмотренных в этом уроке.
Итоги урока
В этом уроке вы узнали, что union по рангу всегда присоединяет более мелкое дерево к более глубокому, ранг увеличивается только при слиянии двух деревьев с одинаковым рангом, поддерживая высоту дерева на уровне O(log n), а сочетание сжатия путей с union по рангу даёт амортизированную сложность O(alpha(n)) — фактически постоянное время. Далее мы применим полный оптимальный DSU к задаче об избыточном ребре и обнаружению циклов в графах.
Часто задаваемые вопросы
Урок «Объединение по рангу и оценка обратной функции Аккермана» бесплатный?
Да — полный текст урока «Объединение по рангу и оценка обратной функции Аккермана» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Объединение по рангу и оценка обратной функции Аккермана»?
Добавьте объединение по рангу, чтобы сохранять деревья плоскими, и разберитесь, почему совокупная оптимизация даёт амортизированное O(alpha(n)), то есть фактически константное время Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Объединение по рангу и оценка обратной функции Аккермана»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- DSU со сжатием путей
- Объединение по рангу и оценка обратной функции Аккермана
- Избыточное ребро и обнаружение циклов
- Объединение аккаунтов и компоненты связности