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.