Puentes y puntos de articulación
Encuentre las aristas y nodos cuya eliminación desconecta el grafo
Puentes y puntos de articulación es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 4 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.
Puntos frágiles en un grafo
Algunas partes de un grafo no dirigido son críticas: al eliminarlas, el grafo se divide. Encontrarlas revela sus puntos débiles.
Qué es un puente
Un puente es una arista cuya eliminación aumenta el número de componentes conexos. Es el único camino entre dos regiones.
Qué es un punto de articulación
Un punto de articulación es un nodo cuya eliminación desconecta el grafo. Las redes son vulnerables a estos puntos únicos de fallo.
Los árboles DFS, de nuevo
Ambos algoritmos se basan en un único DFS y registran el tiempo de descubrimiento y un valor low, de forma parecida a Tarjan, pero en un grafo no dirigido.
disc = [-1] * n
low = [-1] * nLow indica el alcance más antiguo
El low de un nodo es el identificador de descubrimiento más antiguo que se puede alcanzar desde su subárbol DFS, posiblemente mediante una arista de retorno hacia arriba.
Inicializar al entrar
Cuando DFS entra en un nodo, establezca su disc y low con el valor actual del temporizador y avance hacia sus vecinos.
disc[u] = low[u] = timer
timer += 1La condición de puente
Después de recurrir en el hijo v, si low[v] > disc[u], ninguna arista de retorno salta más allá de u, por lo que la arista u-v es un puente.
if low[v] > disc[u]:
bridges.append((u, v))La condición de articulación
Un u que no sea la raíz es un punto de articulación cuando un hijo v cumple low[v] >= disc[u]: el subárbol de v no puede evitar u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)El caso especial de la raíz
La raíz de DFS es un punto de articulación únicamente si tiene dos o más hijos en el árbol DFS, así que debe contarlos.
if parent[u] == -1 and children > 1:
art.add(u)Omitir la arista al padre
Al actualizar low a partir de una arista de retorno, no vuelva a recorrer la arista hacia su padre, o evaluará mal los puentes.
if v != parent[u]:
low[u] = min(low[u], disc[v])Una pasada, dos respuestas
Un único DFS encuentra todos los puentes y puntos de articulación en O(V + E). No hace falta ningún recorrido adicional.
Comprobación rápida
Después de recurrir en el hijo v desde u, descubre que low[v] > disc[u]. ¿Qué ha encontrado?
Repaso: aristas y nodos críticos
Un único DFS con disc y low lo encuentra todo: low[v] > disc[u] marca un puente, y low[v] >= disc[u] marca un punto de articulación. 🌉
Preguntas frecuentes
¿La lección «Puentes y puntos de articulación» es gratis?
Sí — el texto completo de «Puentes y puntos de articulación» 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 «Puentes y puntos de articulación»?
Encuentre las aristas y nodos cuya eliminación desconecta el grafo 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 4 de 4.
¿Cuánto tiempo toma la lección «Puentes y puntos de articulación»?
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