Union-Find (DSU) — LeetCode на Python: Полный курс

Union-Find (Disjoint Set Union)

Система непересекающихся множеств для эффективного объединения и проверки принадлежности. Path compression + union by rank = O(α(n)) ≈ O(1).

#1. Суть паттерна

Union-Find (DSU) — это структура данных для работы с непересекающимися множествами. Она позволяет эффективно:

Объединять два множества (union)
Проверять принадлежность элемента к множеству (find)
Определять, находятся ли два элемента в одном множестве (connected)

#1.1 Термины

Куча (Heap) — древовидная структура, где родитель больше (max-heap) или меньше (min-heap) детей.

Дерево отрезков (Segment Tree) — структура для диапазонных запросов и обновлений.

Префиксное дерево (Trie) — дерево для хранения строк, где каждый узел представляет префикс.

Система непересекающихся множеств (DSU/Union-Find) — структура для эффективного объединения множеств и проверки принадлежности.

#Когда применять

✅ Подсчёт компонент связности — количество островов, групп связанных элементов
✅ Обнаружение циклов — в неориентированных графах
✅ Проверка связности — соединены ли два узла в графе
✅ Динамическое объединение — когда граф меняется (добавляются рёбра)
✅ Эквивалентность — транзитивные отношения (если A~~B и B~~C, то A~C)

#Предусловия

Непересекающиеся множества — каждый элемент принадлежит ровно одному множеству
Операции union/find — основные операции структуры
Оптимизации — path compression и union by rank для O(α(n))

#Структура

Дерево 1:        Дерево 2:
    4               5
   / \              |
  1   3             6
 /
2

parent = [0, 1, 1, 4, 4, 5, 5]  # parent[i] = родитель узла i
rank   = [0, 1, 0, 0, 2, 1, 0]  # rank[i] = высота дерева

#Сравнение с альтернативами

Задача	Union-Find	DFS/BFS	Floyd-Warshall
Компоненты связности	✅ O(m × α(n))	✅ O(n + m)	❌ O(n³)
Динамический граф	✅ Да	❌ Нет	❌ Нет
Проверка связности пары	✅ O(α(n))	❌ O(n + m)	✅ O(1)
Реализация	⚠️ Средняя	✅ Простая	✅ Простая

Вывод: Union-Find лучше для динамических графов и множественных запросов связности.

#2. Шаблон

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = 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):
        rootX, rootY = self.find(x), self.find(y)

        if rootX == rootY:
            return False

        # Union by rank
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX

        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        self.components -= 1

        return True

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

#3. Разбор задач

#Задача 1: Number of Provinces (LeetCode 547) 🟦 Medium

Ссылка: https://leetcode.com/problems/number-of-provinces/

Условие: Дана матрица смежности isConnected размера n x n, где isConnected[i][j] = 1, если город i напрямую соединён с городом j.

Верните количество провинций. Провинция — группа городов, соединённых напрямую или косвенно.

Примеры:

Ввод: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Вывод: 2

Ввод: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Вывод: 3

Ограничения:

1 <= n <= 200
isConnected.length == n
isConnected[i].length == n
isConnected[i][j] — 0 или 1

💡 Подсказка: Используйте Union-Find для объединения соединённых городов. Количество компонент = количество провинций.

#Визуализация

Изначально: 5 элементов (каждый — отдельное множество)
[0] [1] [2] [3] [4]
parent = [0, 1, 2, 3, 4]

Шаг 1: union(0, 1)
[0→1] [2] [3] [4]
parent = [1, 1, 2, 3, 4]
Компоненты: {0,1}, {2}, {3}, {4}

Шаг 2: union(1, 2)
[0→1→2] [3] [4]
parent = [1, 2, 2, 3, 4]
Компоненты: {0,1,2}, {3}, {4}

Шаг 3: union(3, 4)
[0→1→2] [3→4]
parent = [1, 2, 2, 4, 4]
Компоненты: {0,1,2}, {3,4}

Шаг 4: union(2, 4) — объединяем компоненты
[0→1→2→4←3]
parent = [1, 2, 4, 4, 4]
Компоненты: {0,1,2,3,4} — все в одном множестве!

find(0): 0→1→2→4 (возвращает 4)
find(3): 3→4 (возвращает 4)
connected(0, 3): True (оба имеют корень 4)

Решение:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX
        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        self.components -= 1
        return True

def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)

    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                uf.union(i, j)

    return uf.components

Объяснение:

Инициализируем Union-Find с n компонентами
Для каждой пары соединённых городов делаем union
Количество компонент = количество провинций

Сложность:

Время: O(n² × α(n))
Память: O(n)

#Задача 2: Redundant Connection (LeetCode 684) 🟦 Medium

Ссылка: https://leetcode.com/problems/redundant-connection/

Условие: Дано дерево с n узлами (помечены от 1 до n) и одним дополнительным ребром. Верните ребро, которое можно удалить, чтобы получить дерево.

Если есть несколько ответов, верните последнее ребро во входном массиве.

Примеры:

Ввод: edges = [[1,2],[1,3],[2,3]]
Вывод: [2,3]

Ввод: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Вывод: [1,4]

Ограничения:

n == edges.length
3 <= n <= 1000
edges[i].length == 2

💡 Подсказка: Проходите по рёбрам. Первое ребро, где union() возвращает False (корни совпали), создаёт цикл.

#Визуализация

До path compression:
    4
   /|\
  1 2 3
 /
0

find(0): 0→1→4 (длина пути = 2)

После path compression:
    4
   /| \
  0 1  2 3

find(0): 0→4 (длина пути = 1, узел 0 подключён напрямую к корню!)

Решение:

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

    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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX
        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        return True

def findRedundantConnection(edges):
    uf = UnionFind(len(edges))

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]

Объяснение:

Проходим по рёбрам в порядке входа
Если union(u, v) возвращает False — u и v уже в одном множестве
Это ребро создаёт цикл — оно избыточно

Сложность:

Время: O(n × α(n))
Память: O(n)

#Задача 3: Graph Validity (LeetCode 261 — аналог) 🟦 Medium

Ссылка: https://leetcode.com/problems/graph-validity/ (премиум)

Условие: Дано n узлов и список рёбер. Определите, образует ли граф валидное дерево.

Валидное дерево должно:

Иметь ровно n-1 рёбер
Быть связным (1 компонента)
Не иметь циклов

Примеры:

Ввод: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Вывод: true

Ввод: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Вывод: false

Ограничения:

1 <= n <= 2000
0 <= edges.length <= 5000

💡 Подсказка: Проверьте: 1) Количество рёбер = n-1. 2) Нет циклов (union возвращает False). 3) Одна компонента.

Решение:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX
        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        self.components -= 1
        return True

def validTree(n, edges):
    # Дерево должно иметь ровно n-1 ребро
    if len(edges) != n - 1:
        return False

    uf = UnionFind(n)

    for u, v in edges:
        if not uf.union(u, v):
            return False  # Обнаружен цикл

    return uf.components == 1

Объяснение:

Проверка n-1 рёбер — необходимое условие для дерева
Если union возвращает False — есть цикл
components == 1 — граф связный

Сложность:

Время: O(n × α(n))
Память: O(n)

#Задача 4: Accounts Merge (LeetCode 721) 🟦 Medium

Ссылка: https://leetcode.com/problems/accounts-merge/

Условие: Дан список аккаунтов, где каждый аккаунт — список строк: первое имя, затем email.

Аккаунты с общими email принадлежат одному человеку. Объедините аккаунты и верните список в формате: [имя, отсортированные email].

Примеры:

Ввод: accounts = [
  ["John","johnsmith@mail.com","john_newyork@mail.com"],
  ["John","johnsmith@mail.com","john00@mail.com"],
  ["Mary","mary@mail.com"]
]
Вывод: [
  ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
  ["Mary","mary@mail.com"]
]

Ограничения:

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30

💡 Подсказка: Используйте Union-Find. Для каждого email храните индекс аккаунта. Если email встречается снова — объединяйте аккаунты.

Решение:

import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                rootX, rootY = rootY, rootX
            self.parent[rootY] = rootX
            self.rank[rootX] += self.rank[rootX] == self.rank[rootY]

def accountsMerge(accounts):
    uf = UnionFind(len(accounts))
    email_to_account = {}

    # Объединяем аккаунты с общими email
    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_to_account:
                uf.union(i, email_to_account[email])
            else:
                email_to_account[email] = i

    # Группируем email по корневому аккаунту
    emails_by_account = collections.defaultdict(list)
    for email, account in email_to_account.items():
        root = uf.find(account)
        emails_by_account[root].append(email)

    # Формируем результат
    result = []
    for account_idx, emails in emails_by_account.items():
        result.append([accounts[account_idx][0]] + sorted(emails))

    return result

Объяснение:

email_to_account[email] = индекс аккаунта
Если email встречается в другом аккаунте — делаем union
Группируем email по корневому аккаунту, сортируем

Сложность:

Время: O(n × m × log(n × m)), где m — среднее количество email
Память: O(n × m)

#Задача 5: Remove Max Number of Edges (LeetCode 1579) 🔴 Hard

Ссылка: https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/

Условие: Дан неориентированный граф с n узлами и рёбрами трёх типов:

Тип 1: может использовать Alice
Тип 2: может использовать Bob
Тип 3: могут использовать оба

Верните максимальное количество рёбер, которые можно удалить, чтобы и Alice, и Bob могли полностью traversровать граф. Если невозможно, верните -1.

Примеры:

Ввод: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Вывод: 2

Ограничения:

1 <= n <= 10⁵
1 <= edges.length <= min(10⁵, 3 × n × (n-1) / 2)

💡 Подсказка: Приоритет рёбрам типа 3. Сначала обрабатываем их, затем типа 1 (Alice) и типа 2 (Bob).

Решение:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX
        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        self.components -= 1
        return True

def maxNumEdgesToRemove(n, edges):
    uf_alice = UnionFind(n)
    uf_bob = UnionFind(n)
    used = 0

    # Тип 3 (оба) — приоритет
    for t, u, v in edges:
        if t == 3:
            if uf_alice.union(u, v):
                uf_bob.union(u, v)
                used += 1

    # Тип 1 (Alice) и 2 (Bob)
    for t, u, v in edges:
        if t == 1 and uf_alice.union(u, v):
            used += 1
        elif t == 2 and uf_bob.union(u, v):
            used += 1

    # Проверка связности
    if uf_alice.components > 1 or uf_bob.components > 1:
        return -1

    return len(edges) - used

Объяснение:

Два Union-Find: для Alice и Bob
Сначала обрабатываем рёбра типа 3 (общие)
Затем типа 1 и 2
Удаляемые рёбра = total - использованные

Сложность:

Время: O(m × α(n))
Память: O(n)

#Задача 6: Surrounded Regions (LeetCode 130) 🟦 Medium

Ссылка: https://leetcode.com/problems/surrounded-regions/

Условие: Дана доска m x n, заполненная 'X' и 'O'. Захватите все области, окружённые 'X', заменив 'O' на 'X'.

Область захватывается, если она не соединена с границей доски.

Примеры:

Ввод: board = [
  ["X","X","X","X"],
  ["X","O","O","X"],
  ["X","X","O","X"],
  ["X","O","X","X"]
]
Вывод: [
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","O","X","X"]
]

Ограничения:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] — 'X' или 'O'

💡 Подсказка: Используйте dummy узел для границы. Все 'O' на границе объединяйте с dummy. Затем 'O', не connected с dummy, заполняйте 'X'.

Решение:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                rootX, rootY = rootY, rootX
            self.parent[rootY] = rootX

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

def solve(board):
    if not board:
        return

    m, n = len(board), len(board[0])
    uf = UnionFind(m * n + 1)  # +1 для dummy
    dummy = m * n

    def idx(r, c):
        return r * n + c

    # Объединяем 'O' с соседями и с dummy если на границе
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                if i == 0 or i == m-1 or j == 0 or j == n-1:
                    uf.union(idx(i, j), dummy)
                else:
                    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                        ni, nj = i + dr, j + dc
                        if board[ni][nj] == 'O':
                            uf.union(idx(i, j), idx(ni, nj))

    # Заполняем 'O', не connected с dummy
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O' and not uf.connected(idx(i, j), dummy):
                board[i][j] = 'X'

Объяснение:

dummy узел (индекс m×n) представляет все граничные 'O'
Все 'O' на границе объединяем с dummy
'O', не connected с dummy, заполняем 'X'

Сложность:

Время: O(m × n × α(m×n))
Память: O(m × n)

#4. Шпаргалка

Задача	Ключевая идея
Number of Provinces	Подсчёт компонент
Redundant Connection	Первое ребро, где union() = False
Valid Tree	n-1 рёбер + 1 компонента
Accounts Merge	union по email
Remove Max Edges	Приоритет типу 3
Surrounded Regions	union с boundary dummy

#5. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли path compression

Проблема: Без path compression сложность find() становится O(n).

# ❌ Неправильно — нет path compression
def find(self, x):
    if self.parent[x] != x:
        return self.find(self.parent[x])  # Просто рекурсия!
    return self.parent[x]
# Дерево может выродиться в цепочку O(n)

# ✅ Правильно — с path compression
def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Path compression!
    return self.parent[x]
# Амортизированно O(α(n)) ≈ O(1)

Почему это неправильно: Без path compression дерево может выродиться в цепочку.

Как обнаружить: Time Limit Exceeded на больших тестах.

Как исправить: Добавьте self.parent[x] = self.find(self.parent[x]).

#❌ Ошибка 2: Забыли union by rank

Проблема: Без union by rank дерево может стать несбалансированным.

# ❌ Неправильно — нет union by rank
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    if rootX != rootY:
        self.parent[rootY] = rootX  # Просто прикрепляем!
    # Может стать несбалансированным

# ✅ Правильно — с union by rank
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    if rootX == rootY:
        return False
    
    if self.rank[rootX] < self.rank[rootY]:
        rootX, rootY = rootY, rootX
    
    self.parent[rootY] = rootX
    self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
    self.components -= 1
    return True

Почему это неправильно: Несбалансированное дерево ухудшает производительность.

#❌ Ошибка 3: Неправильный подсчёт компонент

Проблема: Не уменьшаем счётчик компонент при объединении.

# ❌ Неправильно — забыли уменьшить components
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    if rootX != rootY:
        self.parent[rootY] = rootX
        # components -= 1 забыли!

# ✅ Правильно
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    if rootX == rootY:
        return False
    self.parent[rootY] = rootX
    self.components -= 1  # Уменьшаем!
    return True

Почему это неправильно: components будет завышен.

#❌ Ошибка 4: Неправильная инициализация

Проблема: Неправильная инициализация parent или rank.

# ❌ Неправильно — parent[i] = 0 для всех
self.parent = [0] * n  # Все указывают на 0!

# ✅ Правильно — каждый элемент — свой корень
self.parent = list(range(n))  # parent[i] = i

Почему это неправильно: Все элементы будут в одном множестве с начала.

#❌ Ошибка 5: Использование без проверки корней

Проблема: Объединение без проверки, что корни разные.

# ❌ Неправильно — нет проверки rootX == rootY
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    self.parent[rootY] = rootX  # Всегда объединяем!
    # components уменьшится даже если уже в одном множестве

# ✅ Правильно — проверка
def union(self, x, y):
    rootX, rootY = self.find(x), self.find(y)
    if rootX == rootY:
        return False  # Уже в одном множестве!
    self.parent[rootY] = rootX
    self.components -= 1
    return True

Почему это неправильно: components станет отрицательным.

#6. 🎯 Попробуйте сами

#Задача для самостоятельного решения

Условие: Дан неориентированный граф с n вершинами и список рёбер. Определите, является ли граф деревом (связный граф без циклов).

Пример:

Ввод: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Вывод: True
Объяснение: Граф связный и без циклов

Ввод: n = 4, edges = [[0,1],[1,2],[2,0],[0,3]]
Вывод: False
Объяснение: Есть цикл 0-1-2-0

💡 Подсказка 1

Дерево должно иметь ровно n-1 ребро

💡 Подсказка 2

Используйте Union-Find для обнаружения циклов

💡 Подсказка 3

Если union() возвращает False — есть цикл

✅ Решение

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False  # Цикл!
        if self.rank[rootX] < self.rank[rootY]:
            rootX, rootY = rootY, rootX
        self.parent[rootY] = rootX
        self.rank[rootX] += self.rank[rootX] == self.rank[rootY]
        self.components -= 1
        return True

def validTree(n, edges):
    # Дерево должно иметь ровно n-1 ребро
    if len(edges) != n - 1:
        return False
    
    uf = UnionFind(n)
    
    for u, v in edges:
        if not uf.union(u, v):  # Если уже в одном множестве — цикл!
            return False
    
    return uf.components == 1  # Должна быть 1 компонента

Объяснение:

Проверяем количество рёбер: должно быть n-1
Используем Union-Find для объединения вершин
Если union() возвращает False — обнаружили цикл
В конце проверяем, что осталась 1 компонента

Сложность:

Время: O(n × α(n)) ≈ O(n)
Память: O(n)

#7. Заключение

Union-Find эффективен для:

Подсчёта компонент связности
Обнаружения циклов
Динамического объединения множеств

Оптимизации:

Path compression — уменьшает высоту дерева
Union by rank — прикрепляет меньшее к большему

Сложность: O(α(n)) ≈ O(1) на операцию.

Дерево 1: Дерево 2: 4 5 / \ | 1 3 6 / 2 parent = [0, 1, 1, 4, 4, 5, 5] # parent[i] = родитель узла i rank = [0, 1, 0, 0, 2, 1, 0] # rank[i] = высота дерева

Задача

Union-Find

DFS/BFS

Floyd-Warshall

Компоненты связности

✅ O(m × α(n))

✅ O(n + m)

❌ O(n³)

Динамический граф

✅ Да

❌ Нет

Проверка связности пары

✅ O(α(n))

❌ O(n + m)

✅ O(1)

Реализация

⚠️ Средняя

✅ Простая

Изначально: 5 элементов (каждый — отдельное множество) [0] [1] [2] [3] [4] parent = [0, 1, 2, 3, 4] Шаг 1: union(0, 1) [0→1] [2] [3] [4] parent = [1, 1, 2, 3, 4] Компоненты: {0,1}, {2}, {3}, {4} Шаг 2: union(1, 2) [0→1→2] [3] [4] parent = [1, 2, 2, 3, 4] Компоненты: {0,1,2}, {3}, {4} Шаг 3: union(3, 4) [0→1→2] [3→4] parent = [1, 2, 2, 4, 4] Компоненты: {0,1,2}, {3,4} Шаг 4: union(2, 4) — объединяем компоненты [0→1→2→4←3] parent = [1, 2, 4, 4, 4] Компоненты: {0,1,2,3,4} — все в одном множестве! find(0): 0→1→2→4 (возвращает 4) find(3): 3→4 (возвращает 4) connected(0, 3): True (оба имеют корень 4)

До path compression: 4 /|\ 1 2 3 / 0 find(0): 0→1→4 (длина пути = 2) После path compression: 4 /| \ 0 1 2 3 find(0): 0→4 (длина пути = 1, узел 0 подключён напрямую к корню!)

Ввод: accounts = [ ["John","johnsmith@mail.com","john_newyork@mail.com"], ["John","johnsmith@mail.com","john00@mail.com"], ["Mary","mary@mail.com"] ] Вывод: [ ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"], ["Mary","mary@mail.com"] ]

Ввод: board = [ ["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"] ] Вывод: [ ["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"] ]

Задача

Ключевая идея

Number of Provinces

Подсчёт компонент

Redundant Connection

Первое ребро, где union() = False

Valid Tree

n-1 рёбер + 1 компонента

Accounts Merge

union по email

Remove Max Edges

Приоритет типу 3

Surrounded Regions

union с boundary dummy

Ввод: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Вывод: True Объяснение: Граф связный и без циклов Ввод: n = 4, edges = [[0,1],[1,2],[2,0],[0,3]] Вывод: False Объяснение: Есть цикл 0-1-2-0