По поводу Википедии -- у неё алгоритм тот же с точностью до шага инвертирования. По 3 лемме неважно, на исходном графе мы проставляем метки, или на инвертированном. Главное -- чтобы во второй DFS мы шли по меткам в обратном порядке в графе, который инвертирован относительно первого прохода DFS.
У меня первый DFS по исходному графу, а воторой -- по инвертированному.
У Википедии первый DFS по инвертированному, второй -- по исходному.
... квадратичный поиск (quadratic probing). Идея в том, что мы после первого обнаруженного занятого места, смотрим в следующее. Если и оно занято, то смотрим не в следующее, а через одно. Если и там занято, то через два и т. д.
Не понимаю, в чём "квадратичность" такого поиска? Если перейти по ссылке, там будет пример скорее, как через 1, через 4, через 9 и т.д. Похожую схему Вы использовали при вычислении ближайшего размера, кратного степени двойки. Но вот поиск мне не показался таковым.
Рад, что статья пригодилась)
По поводу Википедии -- у неё алгоритм тот же с точностью до шага инвертирования. По 3 лемме неважно, на исходном графе мы проставляем метки, или на инвертированном. Главное -- чтобы во второй DFS мы шли по меткам в обратном порядке в графе, который инвертирован относительно первого прохода DFS.
У меня первый DFS по исходному графу, а воторой -- по инвертированному.
У Википедии первый DFS по инвертированному, второй -- по исходному.
Понял. Формула подсчёта:
.Описанное возможно при 
. Тогда как раз получается 
. Что эквивалентно 
Не понимаю, в чём "квадратичность" такого поиска? Если перейти по ссылке, там будет пример скорее, как через 1, через 4, через 9 и т.д. Похожую схему Вы использовали при вычислении ближайшего размера, кратного степени двойки. Но вот поиск мне не показался таковым.