Теорема Менгера: как найти максимальное число рёберно-непересекающихся путей между двумя вершинами?

Теорема Менгера (рёберная форма): максимальное число рёберно-непересекающихся путей между $s$ и $t$ равно минимальному числу рёбер, удаление которых разъединяет $s$ и $t$ (минимальному рёберному разрезу).

Сведение к потоку. Присваиваем каждому ребру пропускную способность 1 и считаем максимальный поток из $s$ в $t$. Поскольку все пропускные единичные, каждый «единичный поток» = один путь, и они автоматически не делят рёбер. Значение потока = число путей.

for(auto&[u,v]:edges) add_edge(u, v, 1); // ориентированный случай
int paths = maxflow(s, t);

Для неориентированного графа ребро $\{u,v\}$ моделируется двумя ориентированными $u\to v$ и $v\to u$, каждое пропускной 1 (или одним ребром cap=1 в обе стороны — зависит от реализации остаточной сети).

Асимптотика: на единичных пропускных Диниц даёт $O(E\sqrt{E})$ (а для разреженных — фактически очень быстро). min-cut величины $k$ ⟺ ровно $k$ путей.

Восстановление самих путей: после maxflow ищем пути жадным DFS по рёбрам с пущенным потоком (где течёт 1), удаляя использованные рёбра. Получите ровно paths путей.