0Pricing
DSA Interview Prep · Урок

DSU со сжатием путей

Реализуйте find со сжатием путей, чтобы все узлы на пути указывали непосредственно на корень, и получите амортизированное время find, близкое к O(1)

«DSU со сжатием путей» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Что такое непересекающиеся множества

DSU, также называемая структурой «объединение и поиск», — это структура данных, поддерживающая набор непересекающихся (не пересекающихся между собой) множеств. Она поддерживает две основные операции: find (какому множеству принадлежит элемент x?) и union (объединить множества, содержащие x и y). DSU идеально подходит для задач о динамической связности, в которых группы со временем объединяются, но никогда не разделяются.

Изначально каждый элемент образует собственное множество. По мере обработки рёбер или связей мы объединяем множества. Сложность заключается в эффективном выполнении этих операций: наивные реализации требуют O(n) на операцию, но с оптимизациями можно приблизиться к амортизированной сложности O(1).

# Naive DSU without optimisations
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own parent

    def find(self, x):
        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:
            self.parent[px] = py

Проблема наивного find

В наивной структуре DSU операция find(x) поднимается по цепочке родителей, пока не достигает узла, который указывает на самого себя (корень). Если дерево сбалансировано, это O(log n). Но если мы всегда выполняем union, подвешивая второй корень под первый, можно создать цепочку (вырожденное дерево) длиной n, из-за чего каждый вызов find будет занимать O(n).

Рассмотрим последовательное объединение 0→1→2→3→4. Вызов find для узла 0 должен пройти всю цепочку. Благодаря сжатию путей мы устраняем эту проблему, заставляя каждый посещённый узел указывать непосредственно на корень уже во время самой операции find.

# Worst case without compression: a chain
# parent = [1, 2, 3, 4, 4]  => find(0) takes 4 steps
# After path compression: parent = [4, 4, 4, 4, 4]  => find(0) takes 1 step

parent = [1, 2, 3, 4, 4]
print('Before:', parent)
# Simulate find(0) with naive approach
x = 0
steps = 0
while parent[x] != x:
    x = parent[x]
    steps += 1
print('Root:', x, 'Steps taken:', steps)

Сжатие путей: рекурсивный однопроходный вариант

Сжатие путей изменяет операцию find так, что после нахождения корня каждый узел на пути начинает указывать непосредственно на корень. Будущие вызовы find для этих узлов выполняются за O(1). Рекурсивная версия элегантно реализует это за один проход.

Ключевая идея: после того как рекурсивный вызов возвращает корень, перед возвратом мы присваиваем self.parent[x] = root. Это выпрямляет дерево — все узлы на пути поиска теперь указывают непосредственно на корень. Принадлежность узла к множеству не меняется; сокращаются только пути поиска при будущих обращениях.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    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:
            self.parent[px] = py

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(2, 3)
print('Root of 0:', dsu.find(0))
print('Parent array after compression:', dsu.parent)

Сжатие путей: итеративный двухпроходный вариант

Итеративная версия сжатия путей использует два прохода: во время первого проходит вверх до корня, а во время второго повторно посещает каждый узел на пути и напрямую обновляет его родителя, указывая на корень. Это позволяет избежать накладных расходов стека рекурсии и безопасно работает с очень глубокими деревьями, близкими к ограничению рекурсии Python.

В рекурсивном и итеративном подходах корректность не меняется — find по-прежнему возвращает тот же корень. Разница лишь в том, что указатели на родителей обновляются как побочный эффект, благодаря чему все будущие вызовы find для этих узлов выполняются за O(1).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]          # first pass: find root
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root             # second pass: compress
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False  # already connected

dsu = DSU(6)
for a, b in [(0,1),(1,2),(2,3),(3,4)]:
    dsu.union(a, b)
print('Parent before find(0):', dsu.parent[:])
dsu.find(0)
print('Parent after  find(0):', dsu.parent[:])

Амортизированная сложность сжатия путей

Одно лишь сжатие путей обеспечивает амортизированное время O(log n) на операцию в последовательности из m операций. При первом прохождении цепочки отдельная операция find может быть дорогой, но она выпрямляет эту цепочку, поэтому каждый последующий вызов find для этих узлов выполняется за O(1). Общая работа распределяется между множеством операций.

Формальный анализ использует метод потенциальной функции: потенциал DSU уменьшается каждый раз, когда укорачивается путь от узла к родителю, и это уменьшение компенсирует стоимость обхода. Без union по рангу одно лишь сжатие путей даёт амортизированную сложность O(log n) — уже огромное улучшение по сравнению с наивным O(n).

# Demonstrating amortised benefit
import time

def build_chain(n):
    parent = list(range(n))
    for i in range(n - 1):
        parent[i] = i + 1  # chain: 0->1->2->...->n-1
    return parent

n = 1000
parent = build_chain(n)

# First find on a chain: visits n nodes
x = 0
root = x
while parent[root] != root:
    root = parent[root]
# Compress
while parent[x] != root:
    nxt = parent[x]; parent[x] = root; x = nxt
print('After first find, parent[0]:', parent[0])  # should be n-1
print('Second find cost: O(1) since parent[0] is now the root')

Подсчёт связных компонент

Распространённое применение DSU — подсчёт связных компонент графа. Мы инициализируем счётчик components значением n — по одному на узел. Каждый успешный union (объединение двух разных множеств) уменьшает счётчик на 1. В конце счётчик содержит количество различных компонент.

Это эффективнее, чем выполнять BFS или DFS для запросов связности, особенно когда рёбра поступают постепенно (онлайн). DSU обрабатывает каждое ребро почти за O(1) в амортизированном смысле независимо от момента его поступления.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.components = 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
        self.parent[px] = py
        self.components -= 1
        return True

dsu = DSU(7)
edges = [(0,1),(1,2),(3,4),(5,6)]
for u, v in edges:
    dsu.union(u, v)
print('Components:', dsu.components)  # 4: {0,1,2}, {3,4}, {5,6}, {6 alone was merged}
# Node 6 is alone => 4 total: {0,1,2},{3,4},{5,6},{6} wait
# Let me recalculate: 7 nodes, 4 edges merged 4 pairs => 7-4=3... no
# {0,1,2} one union, {3,4} one, {5,6} one => 7-3=4 components
print('Expected: 4')

DSU для задач на графы: количество провинций

В задаче «Количество провинций» дана матрица смежности n×n, и требуется определить, сколько существует групп напрямую или косвенно связанных городов. Это в точности задача о связных компонентах, которую DSU решает простым способом. Мы перебираем все пары (i, j), для которых isConnected[i][j] == 1, и вызываем union(i, j).

После обработки всех связей ответом будет dsu.components. Это проще и быстрее, чем запускать BFS из каждого ещё не посещённого узла, а матричное представление обрабатывается напрямую, без предварительного построения списка смежности.

def find_provinces(isConnected):
    n = len(isConnected)
    parent = list(range(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:
            parent[px] = py
            return True
        return False

    count = n
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                if union(i, j):
                    count -= 1
    return count

matrix = [[1,1,0],[1,1,0],[0,0,1]]
print(find_provinces(matrix))  # 2: cities {0,1} and {2}

Варианты сжатия путей: уполовинивание

Помимо двухпроходного сжатия существует более простой однопроходный вариант, называемый уполовиниванием путей: поднимаясь по цепочке, мы заставляем каждый узел указывать на его дедушку, а не на родителя. Это вдвое сокращает длину пути при каждом обходе без второго прохода и обеспечивает такую же амортизированную сложность O(alpha(n)) в сочетании с union по рангу.

Уполовинивание путей часто предпочитают в спортивном программировании, поскольку оно реализуется одним простым циклом без рекурсии и второго обхода. На каждом шаге выполняется self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x].

class DSUHalving:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point to grandparent
            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
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = DSUHalving(8)
for u, v in [(0,1),(2,3),(4,5),(6,7),(0,2),(4,6),(0,4)]:
    dsu.union(u, v)
print('All in one component:', dsu.find(0) == dsu.find(7))

Проверка связности после операций union

Чтобы проверить, являются ли два узла connected (относятся ли они к одной компоненте), вызовите find(x) == find(y). Если оба вызова возвращают один и тот же корень, узлы находятся в одной компоненте. Это запрос connected, который благодаря сжатию путей выполняется почти за O(1) в амортизированном смысле.

В задачах на собеседованиях запросы связности часто перемежаются с операциями union. DSU обрабатывает их онлайн — можно чередовать объединения и запросы в любом порядке. Этим DSU отличается от алгоритмов для статических графов, таких как BFS/DFS: после каждого изменения структуры их необходимо запускать заново.

class DSU:
    def __init__(self, n):
        self.parent = list(range(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:
            self.parent[px] = py

    def connected(self, x, y):
        return self.find(x) == self.find(y)

dsu = DSU(10)
dsu.union(0, 3)
dsu.union(3, 7)
dsu.union(1, 5)
print(dsu.connected(0, 7))   # True: 0-3-7
print(dsu.connected(0, 5))   # False: different components
print(dsu.connected(1, 5))   # True: 1-5

Распространённые ошибки при реализации DSU

Частая ошибка — вызвать find, а затем неправильно изменить parent. Всегда вызывайте find для обоих элементов до проверки равенства — иначе можно некорректно сравнить узел с его собственным корнем. Ещё одна ошибка — забыть, что union ничего не должен делать, если оба элемента уже имеют общий корень.

В Python ограничение глубины рекурсии (по умолчанию 1000) может привести к RecursionError для больших цепочек при рекурсивной реализации find. Используйте итеративную двухпроходную версию, увеличьте ограничение с помощью sys.setrecursionlimit или применяйте итеративное уполовинивание путей, чтобы полностью избежать глубокой рекурсии.

import sys
sys.setrecursionlimit(10000)  # needed for large recursive DSU

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        # Safe iterative path compression
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            nxt = self.parent[x]
            self.parent[x] = root
            x = nxt
        return root

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same component — do nothing
        self.parent[px] = py
        return True

dsu = DSU(5)
print(dsu.union(0, 1))  # True: merged
print(dsu.union(0, 1))  # False: already merged — no double-counting

Отслеживание размеров в DSU

В некоторых задачах требуется знать размер каждой компоненты, а не только её корень. Добавьте массив size, изначально заполненный единицами. При объединении двух компонент прибавляйте размер меньшего корня к размеру большего корня. Это позволяет получать размер компоненты за O(1) после любого union.

Отслеживание размеров также лежит в основе union по размеру (альтернативы union по рангу): всегда подвешивайте меньшее дерево к корню большего дерева. Это гарантирует, что высота дерева остаётся O(log n), и даёт такую же асимптотическую гарантию, как union по рангу.

class DSUWithSize:
    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
        if self.size[px] < self.size[py]:
            px, py = py, px           # attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]

    def get_size(self, x):
        return self.size[self.find(x)]

dsu = DSUWithSize(6)
for u, v in [(0,1),(1,2),(3,4)]:
    dsu.union(u, v)
print('Size of component containing 0:', dsu.get_size(0))  # 3
print('Size of component containing 3:', dsu.get_size(3))  # 2
print('Size of component containing 5:', dsu.get_size(5))  # 1

Быстрая проверка

Проверьте, насколько хорошо Вы поняли концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», рассмотренные в этом уроке.

Итоги урока

В этом уроке Вы узнали: DSU поддерживает непересекающиеся множества с помощью операций find и union, сжатие путей выпрямляет дерево, направляя все пройденные узлы непосредственно к корню, и это обеспечивает для find производительность, близкую к O(1), в амортизированном смысле. Далее мы рассмотрим union по рангу, который удерживает деревья плоскими сверху вниз и обеспечивает оценку через обратную функцию Аккермана.

Часто задаваемые вопросы

Урок «DSU со сжатием путей» бесплатный?

Да — полный текст урока «DSU со сжатием путей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «DSU со сжатием путей»?

Реализуйте find со сжатием путей, чтобы все узлы на пути указывали непосредственно на корень, и получите амортизированное время find, близкое к O(1) Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «DSU со сжатием путей»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. DSU со сжатием путей
  2. Объединение по рангу и оценка обратной функции Аккермана
  3. Избыточное ребро и обнаружение циклов
  4. Объединение аккаунтов и компоненты связности
← Назад к DSA Interview Prep