Strongly Connected Components
Un grafo dirigido tiene n nodos, numerados del 0 al n-1, y una lista de edges, donde [from, to] es una arista del nodo from al nodo to.
Un componente fuertemente conexo es el grupo más grande de nodos en el que cada nodo puede llegar a todos los demás siguiendo las aristas. Cada nodo pertenece exactamente a un componente, y un nodo que no está en ningún ciclo forma un componente por sí solo. Devuelve el número de componentes fuertemente conexos.
Función
- ninteger
- el número de nodos
- edgesinteger-2d-array
- las aristas dirigidas, cada una como [from, to]
- Devuelveinteger
- el número de componentes fuertemente conexas
Restricciones
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [from, to]con0 ≤ from, to < nyfrom ≠ to- No aparece ninguna arista dos veces.
Ejemplos
- Entrada
- n = 6edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
- Salida
- 3
- Explicación
- Los nodos 0, 1 y 2 forman un bucle, así que se alcanzan entre sí. Los nodos 3 y 4 apuntan el uno al otro. El nodo 5 llega al 4, pero nada vuelve al 5, así que queda aislado: 3 componentes.
- Entrada
- n = 5edges = [[1, 0], [0, 1], [2, 3]]
- Salida
- 4
- Explicación
- Los nodos 0 y 1 apuntan el uno al otro y forman un componente. La arista de 2 a 3 va en una sola dirección, así que 2 y 3 están separados, y el nodo 4 no tiene ninguna arista: 4 componentes.
Para ir más allá
¿Cuántas aristas como mínimo tendrías que añadir para que todo el grafo sea un único componente fuertemente conexo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Dos nodos comparten un componente exactamente cuando cada uno puede alcanzar al otro. Una búsqueda desde cada nodo puede comprobarlo, pero recorre las mismas aristas una y otra vez. ¿Qué puede decirte una única búsqueda en profundidad sobre dónde empieza un componente?
Numera los nodos en el orden en que la búsqueda en profundidad los alcanza por primera vez. Para cada nodo, registra también
low: el número más pequeño al que puede llegar bajando por el árbol de búsqueda y luego siguiendo una arista de vuelta hasta un nodo cuyo componente aún está abierto. Un nodo cuyolowes igual a su propio número es el primer nodo de su componente.Mantén los nodos visitados en una pila. Cuando un nodo termine con
lowigual a su propio número, saca elementos de la pila hasta llegar a ese nodo: esos nodos forman un componente, así que cuéntalo. Una prueba hace que la búsqueda alcance una profundidad de 5000 nodos, así que mantén tu propia pila de marcos (nodo, siguiente arista) en lugar de recurrir.
Solución
Reduce cada componente a un punto y los componentes forman un grafo sin ciclos. Los algoritmos de Kosaraju y Tarjan utilizan esto para encontrar todos los componentes en O(n + E), donde E es el número de aristas.
Busca hacia adelante y hacia atrás desde cada nodo
Correcto, pero no termina con las pruebas más grandes
Intuición
Los nodos u y v comparten un componente exactamente cuando cada uno alcanza al otro. Así que, para un nodo s que aún no pertenece a ningún componente, busca hacia delante a lo largo de las aristas y hacia atrás a lo largo de las aristas invertidas. Los nodos encontrados por ambas búsquedas forman su componente. En el primer ejemplo, la búsqueda hacia delante desde 0 encuentra los nodos del 0 al 4 y la búsqueda hacia atrás encuentra 0, 1 y 2, así que {0, 1, 2} es un componente.
Cada componente requiere dos búsquedas en la mayor parte del grafo. En una cadena de 5000 aristas que atraviesa 5001 nodos, cada nodo forma su propio componente, y las búsquedas visitan unos 2.5 × 10^7 nodos.
Algoritmo
- Construye las listas de aristas salientes y entrantes de cada nodo.
- Toma el siguiente nodo
sque no tenga un componente y cuenta un nuevo componente. - Marca lo que
salcanza por las aristas salientes y lo que lo alcanza por las aristas entrantes. - Cada nodo marcado por ambas búsquedas se une al componente de
s. Cuando todos los nodos tengan uno, devuelve el recuento.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
done = [False] * n
# fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
fwd = [-1] * n
bwd = [-1] * n
count = 0
for s in range(n):
if done[s]:
continue
count += 1
# Every node s can reach.
fwd[s] = s
reached = [s]
stack = [s]
while stack:
node = stack.pop()
for nxt in out[node]:
if fwd[nxt] != s:
fwd[nxt] = s
reached.append(nxt)
stack.append(nxt)
# Every node that can reach s.
bwd[s] = s
stack = [s]
while stack:
node = stack.pop()
for prev in rev[node]:
if bwd[prev] != s:
bwd[prev] = s
stack.append(prev)
# The nodes found both ways form the component of s.
for v in reached:
if bwd[v] == s:
done[v] = True
return countAlgoritmo de Kosaraju: dos pasadas
Intuición
En el grafo de componentes, una de ellas es un sumidero, sin aristas que salgan de ella, y una búsqueda iniciada dentro de ella encuentra exactamente esa componente. El algoritmo de Kosaraju ordena las búsquedas para que cada una se comporte así.
La primera pasada enumera cada nodo cuando termina su búsqueda en profundidad. La segunda pasada busca en el grafo invertido, que tiene las mismas componentes, empezando por el último nodo en terminar. Si una arista va de la componente B a la C, el último nodo de B termina después de todos los de C. Así que, cuando la segunda pasada llega a C, todas las componentes con una arista hacia C ya están asignadas, y en el grafo invertido la búsqueda no puede salir de C.
En el primer ejemplo, los nodos terminan en el orden 4, 3, 2, 1, 0, 5. La segunda pasada reúne {5}, luego {0, 1, 2} y después {3, 4}.
Algoritmo
- Construye las listas de aristas salientes y entrantes.
- Ejecuta una búsqueda en profundidad iterativa desde cada nodo no visitado y añade cada nodo a
ordercuando termine. - Recorre
orderdesde el final. Para cada nodo que no tenga un componente, cuenta uno nuevo y busca desde él a lo largo de las aristas entrantes, asignando cada nodo sin asignar al que llegue. Devuelve el recuento.
def countSCC(n, edges):
out = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
rev[b].append(a)
# Pass 1: depth first search on the graph, listing each node when it finishes.
seen = [False] * n
order = []
for start in range(n):
if seen[start]:
continue
seen[start] = True
# Each frame is [node, next edge to try].
stack = [[start, 0]]
while stack:
frame = stack[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if not seen[nxt]:
seen[nxt] = True
stack.append([nxt, 0])
else:
stack.pop()
order.append(node)
# Pass 2: on the reversed graph, start from the last node to finish.
# Each search collects exactly one component.
done = [False] * n
count = 0
for start in reversed(order):
if done[start]:
continue
count += 1
done[start] = True
stack = [start]
while stack:
node = stack.pop()
for prev in rev[node]:
if not done[prev]:
done[prev] = True
stack.append(prev)
return countAlgoritmo de Tarjan: una pasada con valores bajos
Intuición
Realiza una búsqueda en profundidad y asigna a cada nodo un número en el orden en que lo alcanzas: su index. Mantén una pila de nodos visitados cuyo componente aún está abierto y un valor low: el índice más pequeño al que un nodo puede llegar bajando por el árbol de búsqueda y luego retrocediendo por una arista hasta un nodo de esa pila.
Cuando un nodo termina con low menor que index, algo situado más abajo vuelve a subir hasta un nodo abierto anterior, así que permanece en la pila. Cuando son iguales, el nodo es el primero al que la búsqueda entró en su componente: desapila hasta llegar a él y cuenta un componente. Una arista que llega a un nodo desapilado conduce a un componente terminado que no puede volver atrás, así que se ignora.
En el primer ejemplo, 3 desapila {4, 3} y 0 desapila {2, 1, 0}. La arista de 5 conduce al 4, que ya fue desapilado, así que 5 se desapila solo.
Algoritmo
- Para cada nodo no visitado, asígnale el siguiente índice, establece
lowcon el mismo valor, añádelo a la pila de nodos y añade el marco (nodo, primera arista). - Si al nodo del marco superior le queda una arista, síguela: un destino no visitado recibe un índice y un marco, y un destino que esté en la pila de nodos reduce
low[node]a su índice. - En caso contrario, extrae el marco y reduce
lowdel padre alow[node]. Silow[node]es igual aindex[node], extrae nodos de la pila hasta llegar al nodo y cuenta un componente.
def countSCC(n, edges):
out = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
index = [-1] * n # discovery time, -1 while unvisited
low = [0] * n # earliest discovery time the node can reach and still return from
on_stack = [False] * n
stack = [] # visited nodes whose component is still open
time = 0
count = 0
for start in range(n):
if index[start] != -1:
continue
index[start] = low[start] = time
time += 1
stack.append(start)
on_stack[start] = True
# The depth first search keeps its own call stack: [node, next edge to try].
calls = [[start, 0]]
while calls:
frame = calls[-1]
node, i = frame
if i < len(out[node]):
frame[1] += 1
nxt = out[node][i]
if index[nxt] == -1:
index[nxt] = low[nxt] = time
time += 1
stack.append(nxt)
on_stack[nxt] = True
calls.append([nxt, 0])
elif on_stack[nxt]:
# An edge back into an open component.
low[node] = min(low[node], index[nxt])
else:
calls.pop()
if calls:
parent = calls[-1][0]
low[parent] = min(low[parent], low[node])
# Nothing below node reaches above it: node closes a component.
if low[node] == index[node]:
count += 1
while True:
w = stack.pop()
on_stack[w] = False
if w == node:
break
return count
Errores comunes y casos límite
- Olvidar los nodos que no tienen aristas. En el segundo ejemplo, el nodo 4 no aparece en ninguna arista y aun así es un componente.
- Reducir
lowa través de cualquier nodo visitado en lugar de hacerlo solo con los que están en la pila. En el primer ejemplo, la arista5 → 4impide entonces que 5 cierre su componente. - Tratar las aristas como bidireccionales. Eso cuenta los componentes conexos: el primer ejemplo daría 1 en lugar de 3.
- Usar recursión en Python. Un ciclo que pasa por 5000 nodos anida 5000 llamadas, cinco veces el límite predeterminado de 1000. Mantén tu propia pila de marcos.
- Ejecutar la segunda pasada de Kosaraju sobre las aristas originales o en el orden en que se visitaron los nodos por primera vez. Cualquiera de las dos opciones fusiona componentes que solo llegan entre sí en una dirección.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de encontrar componentes fuertemente conexas?
Tiempo O(n + E) con el algoritmo de Kosaraju o de Tarjan, ya que cada nodo y arista se procesa un número constante de veces. Ambos usan O(n + E) de espacio para las listas de aristas y las pilas de búsqueda.
¿Deberías usar el algoritmo de Kosaraju o el de Tarjan?
El algoritmo de Kosaraju consiste en dos búsquedas sencillas y es más difícil equivocarse. El de Tarjan necesita una sola búsqueda y no requiere un grafo invertido, a costa de llevar el registro de low.
¿Cuál es la diferencia entre los componentes fuertemente conexos y los componentes conexos?
Los componentes conexos ignoran la dirección de las aristas: dos nodos están conectados cuando algún camino los une. En los componentes fuertemente conexos, cada nodo debe poder llegar al otro. El primer ejemplo es un componente conexo, pero tiene tres componentes fuertemente conexos.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def countSCC(n, edges):
# Escribe el código aquíPrueba #1
Prueba #2
Argumentos
n = 6 edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 3], [5, 4]]
Salida Esperada
3