Componentes Fuertemente Conexos (Tarjan)

Dado un grafo dirigido representado como una lista de adyacencia, encuentra todos los Componentes Fuertemente Conexos (SCC) usando el algoritmo de Tarjan.

Un componente fuertemente conexo es un subconjunto maximal de nodos tal que existe un camino dirigido de cada nodo a todos los demás nodos del subconjunto.

Representación del grafo

El grafo se pasa como un diccionario donde las claves son los nodos (enteros) y los valores son listas de nodos vecinos.

# Grafo con 5 nodos: 0→1, 1→2, 2→0, 1→3, 3→4
graph = {
    0: [1],
    1: [2, 3],
    2: [0],
    3: [4],
    4: []
}

find_sccs(graph)
# → [[0, 1, 2], [3], [4]]

Reglas de salida

• Cada SCC es una lista de nodos ordenada de menor a mayor.
• Los SCCs en el resultado final están ordenados por su elemento mínimo de menor a mayor.

Complejidad esperada

• Tiempo: O(V + E)
• Espacio: O(V)

Casos especiales

• Grafo vacío → []
• Nodo sin aristas → SCC de un solo elemento
• Grafo completamente conexo → un solo SCC con todos los nodos