Componentes fuertemente conexas
Agrupe nodos mutuamente alcanzables con Tarjan
Componentes fuertemente conexas es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Qué es una SCC
Una componente fuertemente conexa es un grupo maximal de nodos en el que cada nodo puede alcanzar cualquier otro siguiendo aristas dirigidas.
Por qué son importantes
Convertir cada SCC en un supernodo transforma cualquier grafo dirigido en un DAG. Así resulta más sencillo razonar sobre las dependencias mutuas.
Tarjan en una sola pasada
El algoritmo de Tarjan encuentra todas las SCC en un único DFS. Se ejecuta en O(V + E), el mismo coste que un recorrido sencillo.
Números de descubrimiento
Asigne a cada nodo un tiempo de descubrimiento según el orden en que DFS lo visita por primera vez. Estos identificadores permiten comparar qué nodo se visitó antes.
disc = [-1] * n
timer = 0El valor low-link
El low-link de cada nodo es el menor identificador de descubrimiento que se puede alcanzar desde él, incluso a través de aristas de retorno. Este valor determina el componente.
low = [-1] * nIntroducir en la pila
Cuando DFS entra en un nodo, establezca su disc y low y después introdúzcalo en una pila de nodos que podrían compartir su componente.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueActualizar low a partir de los hijos
Después de recurrir en un hijo no visitado, propague su valor low hacia arriba: low[u] se convierte en el mínimo entre su valor y el low del hijo.
dfs(v)
low[u] = min(low[u], low[v])Gestionar las aristas de retorno
Si un vecino ya está en la pila, es un antecesor de esta SCC. Use su disc para reducir low[u].
elif on_stack[v]:
low[u] = min(low[u], disc[v])Detectar la raíz de un componente
Cuando low[u] es igual a disc[u], el nodo u es la raíz de una SCC. Todo lo que está por encima de él en la pila pertenece al mismo componente.
Extraer el componente
En una raíz, extraiga nodos de la pila hasta sacar u. El grupo extraído es exactamente una componente fuertemente conexa.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju como alternativa
¿Prefiere dos pasadas? El algoritmo de Kosaraju ejecuta DFS, invierte todas las aristas y vuelve a ejecutar DFS en orden de finalización para extraer las SCC.
Comprobación rápida
Durante el DFS de Tarjan, el nodo u cumple low[u] == disc[u]. ¿Qué le indica esto?
Repaso: SCC con Tarjan
Registre disc y low en un único DFS, mantenga los nodos activos en una pila y extraiga un componente cuando low sea igual a disc. SCC en O(V+E). 🧩
Preguntas frecuentes
¿La lección «Componentes fuertemente conexas» es gratis?
Sí — el texto completo de «Componentes fuertemente conexas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Componentes fuertemente conexas»?
Agrupe nodos mutuamente alcanzables con Tarjan Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Componentes fuertemente conexas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Ordenación topológica con el algoritmo de Kahn
- Detecte ciclos en grafos dirigidos
- Componentes fuertemente conexas
- Puentes y puntos de articulación