Изменения

Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указать указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.

* Для каждой вершины <tex>v</tex> вычислим входящий и исходящий потенциал: <tex>p_{in}=\sum \limits_{u} c(u, v)</tex> и <tex>p_{out}=\sum \limits_{u} c(v, u, v)</tex>. Пусть <tex>p_{in}(s)=\infty</tex> и <tex>p_{out}(t)=\infty</tex>. Определим потенциал или пропускную способность вершины в [[Определение сети, потока|сети]] <tex>p(v)=min(p_{in}(v), p_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через неё проходить. Ясно, что через вершины с <tex>p(v)=0</tex> поток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, дополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удалёнными. Если в результате появятся новые вершины с <tex>p(v)=0</tex>, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с <tex>p(v)\ne0</tex>.

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K= O(V)</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий.