¿Cómo implementarías el algoritmo de Tarjan para componentes fuertemente conexos?

Pregunta y escenario

El grafo tiene n vértices y m aristas dirigidas. Los vértices pueden no tener aristas salientes, las aristas pueden repetirse y no se garantiza que el grafo sea conexo. Un componente fuertemente conexo es un conjunto en el que cada par de vértices puede alcanzarse mutuamente. Devuelve todos los componentes y explica cómo contraerlos forma un grafo acíclico dirigido.

Lo que evalúa el entrevistador

• ¿Puede el candidato mantener correctamente los índices de DFS, los valores de low, la pertenencia a la pila y los ID de componentes?
• ¿Puede distinguir aristas de árbol (tree edges), aristas hacia atrás (back edges) y aristas hacia un componente ya completado al actualizar low?
• ¿Cubre grafos desconectados, bucles hacia sí mismo, aristas paralelas y el riesgo de profundidad de recursión?
• ¿Puede establecer el tiempo O(n+m) y el espacio auxiliar O(n), y verificar los invariantes?

Preguntas de clarificación que conviene hacer primero

Confirma si los ID de los vértices son contiguos, si se permiten aristas paralelas, si los miembros de los componentes deben ordenarse y si el entorno de ejecución limita la profundidad de recursión. Aclara el tamaño del grafo, las necesidades de actualización incremental y si solo se requiere una consulta de pertenencia al mismo componente. Para un grafo muy profundo, expón el balance entre recursión y una pila explícita.

Un marco de respuesta de 30 segundos

Ejecuta un DFS y asigna a cada vértice un índice creciente y el índice más pequeño alcanzable mediante una arista hacia atrás, llamado low. Haz push y marca cada vértice, luego inspecciona los vecinos: realiza la llamada recursiva en un vecino no visitado y usa su low; para un vecino que aún esté en la pila, usa su índice. Cuando low es igual al índice del propio vértice, este es una raíz de componente; haz pop hasta llegar a ese vértice. Cada vértice y arista recibe un trabajo constante, por lo que la complejidad es O(n+m).

Análisis detallado paso a paso

1. Inicializar el estado. Mantén un índice, low, un indicador de pertenencia a la pila y un ID de componente para cada vértice. Inicia el DFS desde cada vértice no visitado para cubrir entradas desconectadas.
2. Procesar un vecino no visitado. Haz la recursión y luego aplica low[u] = min(low[u], low[v]). Esto registra un camino desde el subárbol DFS de regreso a un vértice anterior en la pila.
3. Procesar un vecino en la pila. Si el vecino todavía está en la pila, actualiza low[u] con el índice del vecino. Un vértice que ya fue extraído hacia otro componente no puede participar en este retroceso (backtrack).
4. Encontrar una raíz y extraerla. Cuando low[u] == index[u], u es la raíz. Haz pop y limpia el indicador de pertenencia hasta que se extraiga u; esos vértices forman un componente fuertemente conexo.
5. Manejar casos límite. Un bucle hacia sí mismo aún produce un componente unitario; las aristas paralelas repiten la misma actualización de mínimo; un vértice aislado se convierte en un componente unitario cuando se le hace push.
6. Validar y condensar. Comprueba que cada vértice pertenezca exactamente a un componente y que las aristas entre componentes formen un DAG. Compara grafos pequeños aleatorios con clausura transitiva o Kosaraju, y luego prueba la complejidad y la profundidad de la pila en grafos grandes.

Respuesta de muestra de alta calidad

Mantendría cuatro arreglos: un index creciente, un valor de retroenlace low, un indicador de pertenencia a la pila y un ID de componente. Al ingresar al DFS, asigna un índice y haz push del vértice. Para un vecino no visitado, haz recursión y propaga su valor low; para un vecino que todavía está en la pila, propaga solo el índice de ese vecino. Los componentes completados nunca participan en la actualización.

Cuando low[u] == index[u], u es una raíz, por lo que se hace pop hasta u y se limpian los indicadores. Inicia el DFS desde cada vértice no visitado, de modo que no se asuma conectividad. Cada vértice se inserta (push) y se extrae (pop) una vez, y cada arista se inspecciona una vez, lo que da un tiempo O(n+m) y un espacio auxiliar O(n). Las pruebas cubren bucles hacia sí mismo, aristas paralelas, vértices aislados, cadenas largas, ciclos múltiples y grafos desconectados, además de la partición de componentes y el DAG de condensación.

Errores comunes

• Actualizar a partir del valor low de cada vecino visitado y retroceder accidentalmente a través de un componente completado.
• Olvidar limpiar la pertenencia a la pila después de extraer un componente, por lo que aristas posteriores tratan a vértices antiguos como ancestros actuales.
• Iniciar el DFS desde un solo vértice y omitir componentes en entradas desconectadas.
• Interpretar que low igual al índice actual significa "sin aristas" en lugar de "este vértice es la raíz del componente".
• Superar el límite de la pila del lenguaje sin discutir una pila explícita, procesamiento en bloques o configuración del entorno de ejecución.

Preguntas de seguimiento y respuestas

¿Por qué un vértice extraído de la pila no puede actualizar low?

Ya pertenece a un componente completado y ya no es un ancestro de retroceso en la ruta actual de DFS. Usar su valor low cruzaría los límites de los componentes y destruiría la maximalidad.

¿Cómo demuestras que cada componente se extrae exactamente una vez?

Cada vértice se inserta una vez y solo una raíz puede activar la extracción. Después de la extracción, su indicador de pila se limpia y DFS nunca lo vuelve a insertar, por lo que cada vértice pertenece exactamente a un componente.

¿Cómo eliges entre Tarjan y Kosaraju?

Tarjan utiliza un solo DFS y ningún grafo transpuesto, lo que puede reducir el recorrido y el almacenamiento. Kosaraju utiliza dos pasadas de DFS y separa las etapas con claridad. Ambos son O(n+m); la elección depende de los límites de la pila, la legibilidad y la representación existente del grafo.