Изменения

Определим <tex>R_i</tex> = {<tex>v \bigm|</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\leq i</tex>}.

Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.

Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex>\langle G, s, t \rangle \in \mathrm{NCONN}</tex>.

Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти (это будет доказано ниже).