Redundant Connection

Средняя№684

К дереву на вершинах от 1 до n добавили одно лишнее ребро, и в графе появился ровно один цикл. Даны его n рёбер. Нужно вернуть ребро, после удаления которого останется дерево; если подходят несколько — то, что в списке последнее. Наш пример: [1, 2], [3, 4], [2, 4], [3, 1], [4, 5] → [3, 1].

684 Redundant ConnectionРазбор · 1×

Пример: [1, 2], [3, 4], [2, 4], [3, 1], [4, 5]. Цикл — 1–2–4–3–1, и его последнее в списке ребро, 3–1, соединяет уже связанные вершины. 4–5 идёт после него, но в цикл не входит.

123451122334455parentedges1–23–42–43–14–5
смотрим сейчаскорень группыребро уже добавилиребро, которое замыкает циклне смотрели

Каждая из 5 вершин — сама себе корень. Ячейка 0 не нужна: вершины нумеруются с 1

01/51
сначала · назад · пуск · шаг
Скорость
1function findRedundantConnection(edges):
2 parent = [0, 1, ..., n] // n edges, vertices 1..n
3 for (a, b) in edges:
4 rootA = find(a)
5 rootB = find(b)
6 if rootA == rootB:
7 return [a, b]
8 parent[rootB] = rootA
9
10function find(x):
11 while parent[x] is not x:
12 x = parent[x]
13 return x
состояние
parent
[0, 1, 2, 3, 4, 5]
a
–
b
–
rootA
–
rootB
–
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Пока у концов ребра разные корни, ребро только соединяет две группы и цикла не даёт. Если корень уже общий, рядом с ребром есть путь, и вместе они образуют цикл.
  2. Цикл замыкается только тогда, когда приходит последнее в списке его ребро, поэтому первое такое ребро и есть последнее ребро цикла — то, которое нужно вернуть.
  3. Рёбра после него в цикл не входят, ведь цикл в графе один, поэтому прогон на нём заканчивается.

Сложность

Время O(n · h): два find на ребро глубиной с дерево, здесь до n и почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее. Память O(n) на parent.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.