68
правок
Изменения
→Алгоритм
== Алгоритм ==
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины U и проверять при каждом посещении вершины, не является ли она искомой вершиной V.
Так как в первый момент времени все пути в графе "белые", то если вершина V и была достижима из U, то по [[Лемме Лемма о белых путях|Лемма Лемме о белых путях]] в какой-то момент времени мы зайдём в вершину V, чтобы её покрасить. Время работы алгоритма O(M + N).
=== Реализация ===
