Componentes fuertemente conexos

Grupos maximales de nodos de un grafo dirigido que se alcanzan todos entre sí (y de regreso). Colapsa cada uno → el grafo entero se vuelve un DAG.

Kosaraju: dos pasadas + un truco

• Invertir cada arista conserva los SCC pero voltea los enlaces ENTRE ellos
• Pasada 1: DFS sobre el grafo, registra el orden de finalización
• Pasada 2: DFS sobre el grafo INVERTIDO en orden inverso de finalización
• Cada árbol de la pasada 2 = un SCC. O(V+E).

Mira cómo se revelan los componentes

Las aristas grises entre colores van en un solo sentido — no puedes regresar → componentes separados. {0,1,2} · {3,4} · {5,6,7}, y luego colapsa a un DAG.

Emerge el SCC gigante

Una transición de fase en grado ≈ 1: de 0.2% a 89% de los nodos en un solo componente para el grado 3. (Esto es el "núcleo" de la web.)

Kosaraju vs Tarjan

• Kosaraju: dos pasadas, el más fácil de entender
• Tarjan: una pasada, números low-link, el que usan las librerías
• La misma descomposición — verifica uno contra el otro
• ¿Grafo no dirigido? Usa componentes conexos normales

Para llevar

Razonamiento de orden de finalización (ordenamiento topológico) aplicado a un grafo CÍCLICO vía la transpuesta. Deadlocks, 2-SAT, loops de compilador, el moño de la web — todo son SCC. Bloque de grafos terminado. Siguiente bloque: strings, empezando con KMP.