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 objeto donde las claves son los nodos (números) y los valores son arreglos de nodos vecinos.

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

findSCCs(graph);
// → [[0, 1, 2], [3], [4]]

Reglas de salida

• Cada SCC es un arreglo de nodos ordenado 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