Компоненты сильной связности: алгоритм Тарьяна за один DFS — как работает low-link?

Идея. В DFS каждой вершине даём время входа tin[v]. low[v] — минимальный tin, достижимый из поддерева v, идя по любым рёбрам дерева/назад/вперёд, но только через вершины, ещё лежащие на стеке (т.е. не из уже закрытых SCC). Если low[v] == tin[v], то v — «корень» своей SCC: из поддерева v нельзя «выпрыгнуть» в более раннюю живую вершину, значит всё, что лежит на стеке выше v (включая v), образует одну компоненту.

int timer = 0;
vector<int> tin, low, comp;
vector<bool> onstk;
stack<int> st;
vector<int> g[N];
int scc_cnt = 0;

void dfs(int v) {
    tin[v] = low[v] = timer++;
    st.push(v); onstk[v] = true;
    for (int u : g[v]) {
        if (tin[u] == -1) {              // дерево
            dfs(u);
            low[v] = min(low[v], low[u]);
        } else if (onstk[u]) {           // обратное/перекрёстное в живую вершину
            low[v] = min(low[v], tin[u]);
        }
    }
    if (low[v] == tin[v]) {              // v — корень SCC
        while (true) {
            int u = st.top(); st.pop(); onstk[u] = false;
            comp[u] = scc_cnt;
            if (u == v) break;
        }
        scc_cnt++;
    }
}

Инициализация: tin.assign(n,-1); low.assign(n,0); comp.assign(n,-1); onstk.assign(n,false); и for v: if tin[v]==-1 dfs(v).

Сложность O(V+E), память O(V). Ключевая тонкость — на стеке держим вершины незакрытых SCC; обновлять low по tin[u] можно только если onstk[u], иначе утянем low в чужую компоненту.

Грабля: при больших V замените рекурсию на итеративную (см. вопросы про переполнение стека), глубина может быть V.