Primero una búsqueda en profundidad sobre G que deja los vértices ordenados por tiempo de finalización decreciente; después el mismo recorrido sobre Gᵀ, recorriendo esa lista de izquierda a derecha. Cada llamada que encuentra su vértice sin asignar pinta un componente entero y no se sale de él. El dibujo cambia de G a Gᵀ cuando empieza la segunda pasada.
Entrada: un grafo dirigido en lista de adyacencia, con 8 vértices. Salida: sus componentes fuertemente conexos, en orden topológico del grafo de componentes.
ord?asignar se topan
con un vértice que ya tiene componente y se devuelven sin hacer nada.| Componente | Nombre g | Vértices | Tamaño |
|---|
ord, ¿qué se perdería?Sin solución aquí. En el primer grafo, ejecute la
segunda pasada recorriendo ord al revés, de derecha a
izquierda, y escriba los grupos que salen. Diga en qué paso de la
demostración se rompe el argumento. Después agregue la flecha 7 → 0 y
calcule a mano cuántos componentes quedan.