Функциональный граф (каждая вершина имеет одно исходящее ребро): как найти цикл, в который ведёт путь?
В задаче у каждой вершины ровно одно исходящее ребро next[v] (функциональный граф). Из любой вершины, если идти по стрелкам, рано или поздно попадаешь в цикл. Нужно для каждой вершины понять, на каком шаге она входит в цикл и какой длины цикл. Перебор «иди пока не повторится» на каждой вершине — это O(V²). Как быстрее?
2 ответа
Функциональный граф = «деревья, врастающие в циклы». Каждая компонента — это один цикл (rho-структура: «ро»), к которому подвешены деревья из вершин, ведущих в цикл.
Способ 1 — сначала найти все циклы, потом обработать деревья. Идём итеративным DFS, помечая вершины тремя состояниями (не посещена / в обработке / закрыта). Когда на текущем пути встречаем вершину «в обработке» — нашли цикл, выделяем его. Затем все некольцевые вершины получают dist_to_cycle через обход к уже известным.
Способ 2 — самый практичный: разворот рёбер. Сначала найдём все вершины на циклах, потом обойдём граф «деревьев» в обратную сторону от циклов:
int nxt[N], indeg[N];
// 1) убираем «хвосты» алгоритмом, похожим на топсорт:
// вершины с indeg==0 точно НЕ на цикле — отрезаем, уменьшая indeg[nxt[v]]
queue<int> q;
for (int v=0; v<n; v++) if (indeg[v]==0) q.push(v);
vector<bool> onCycle(n, true);
while (!q.empty()){ int v=q.front(); q.pop(); onCycle[v]=false;
if (--indeg[nxt[v]]==0) q.push(nxt[v]); }
// 2) оставшиеся onCycle==true образуют циклы; их длины и dist до цикла
// считаем обходами по nxt[] / обратным рёбрам
Идея шага 1 — как у Кана: кто не входит ни в один цикл, имеет «висящий хвост» и постепенно indeg обнуляется. Останутся ровно вершины циклов.
Сложность O(V) — каждая вершина обрабатывается константное число раз. Память O(V). Это в разы лучше наивного O(V²).
Если памяти O(V) нет (классическая «найти цикл в последовательности x→f(x)→f(f(x))» при огромном диапазоне значений), применяют алгоритм Флойда «черепаха и заяц» — две скорости:
int t = nxt[s], h = nxt[nxt[s]];
while (t != h) { t = nxt[t]; h = nxt[nxt[h]]; } // встретились в цикле
// затем найти вход в цикл и его длину доп. проходами
O(длины ро) по времени, O(1) по памяти — заходит там, где нельзя хранить used[]. Есть ещё алгоритм Брента (тоже O(1) память, обычно быстрее на константе). Но если вершины пронумерованы 0..n−1 и память O(V) допустима — способ с обрезанием хвостов (как в принятом ответе) проще и обрабатывает все вершины разом, а не один путь.