SCC (Tarjan)

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Componentes fuertemente conexas de un grafo dirigido en una sola pasada de DFS; el id de componente queda en orden topológico inverso.

Complejidad: O(V + E).

Cuándo usarlo

Condensar un dígrafo en un DAG, 2-SAT, detectar ciclos dirigidos, dependencias mutuas.

Implementación recomendada (C++)

struct SCC {
    int n, timer = 0, ncomp = 0;
    vector<vector<int>> g;
    vector<int> num, low, comp; vector<char> on; stack<int> st;  // on[v]: v sigue en la pila
    SCC(int n) : n(n), g(n), num(n,-1), low(n), comp(n,-1), on(n,0) {}
    void add(int u, int v) { g[u].push_back(v); }
    void dfs(int u) {
        num[u] = low[u] = timer++; st.push(u); on[u] = 1;
        for (int v : g[u]) {
            if (num[v] == -1) { dfs(v); low[u] = min(low[u], low[v]); }
            else if (on[v])   low[u] = min(low[u], num[v]);  // ¡num[v], NO low[v]!
        }
        if (low[u] == num[u]) {
            while (true) { int v = st.top(); st.pop(); on[v] = 0; comp[v] = ncomp; if (v == u) break; }
            ncomp++;
        }
    }
    void run() { for (int i = 0; i < n; i++) if (num[i] == -1) dfs(i); }
};

⚠️ Notas

comp[u] da el id de SCC (en orden topológico inverso del DAG condensado). DFS recursivo: para n grande, sube el límite de pila o hazlo iterativo.

🔗 Relacionados