Find if Path Exists in Graph

Лёгкая№1971

Есть n вершин и список неориентированных рёбер. Нужно сказать, можно ли дойти по рёбрам от вершины source до вершины destination. Наш пример: 5 вершин, рёбра 0–1, 2–3, 1–2, от 0 до 3 → true.

1971 Find if Path Exists in GraphРазбор · 1×

Пример: 5 вершин, рёбра 0–1, 2–3, 1–2, source 0, destination 3. Ребра между 0 и 3 нет: путь идёт через 1 и 2.

012340011223344parentedges0–12–31–2source = 0, destination = 3
смотрим сейчаскорень группыребро уже учли

Каждая из 5 вершин — сама себе корень: 5 групп по одной

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

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

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

  1. Ребро кладёт оба своих конца в одну группу, а слияние групп ничего не разбивает, поэтому после всех рёбер группа — это ровно вершины, которые достижимы друг из друга.
  2. Имя группы — её корень. Две вершины в одной группе, когда find даёт им один корень, сколько бы рёбер между ними ни было.
  3. Сами пути не строим: ответ — одно сравнение двух корней.

Сложность

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

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

Решить на LeetCode ↗

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