Изменения

Алгоритм использует <tex>O(\log |G|)</tex> памяти, так необходимо хранить лишь <tex>v</tex>, <tex>u</tex>, <tex>r</tex> и еще поочередно значения полученные в результате вызова <code>'''Enum</code>'''.

Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCONNCONN''' на логарифмической памяти.

Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>'''Next''' </codetex> (n - 1) </tex> раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.

<code> NONCON'''NCONN'''(<tex>G, s, t</tex>) r<subtex>nr_n = 1</subtex> := 1 //''r<subtex>0r_0 = 1</subtex> = 1'' '''for''' <tex>i = 0..(n - 2) </tex> '''do''' //''вычисляем r<subtex>r_{n-1}</subtex>'' r<subtex>nr_n = </subtex> := '''Next'''(<tex>s, i, r<sub>nr_n, G</subtex>, G) '''if''' t (<tex>t1</tex> '''in''' ''' Enum'''(<tex>s, n - 1, r<sub>nr_n, G</subtex>, G) '''then''' ) //''перечисляем вершины из R<subtex>R_{n-1}</subtex>, если <tex>t </tex> была перечислена, то <tex>t </tex> достижима и выдаем REJECT'''reject''', иначе ACCEPT'''accept''' '''REJECTreject'''

'''ACCEPTaccept'''