Conexión redundante y detección de ciclos
Detecte la arista que crea un ciclo en un grafo no dirigido aplicando union a cada arista y comprobando si dos nodos ya están conectados.
Conexión redundante y detección de ciclos es una lección gratuita de DSA Interview Prep 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué es una conexión redundante?
El problema de la conexión redundante (LeetCode 684) proporciona un árbol de n nodos y una arista adicional que forma exactamente un ciclo. Su tarea consiste en encontrar la arista que, al eliminarse, restaura el árbol. Si existen varias respuestas, devuelva la última de la lista de entrada.
Un árbol con n nodos tiene exactamente n-1 aristas y es conexo, sin ciclos. Añadir una arista más crea exactamente un ciclo. La arista añadida (redundante) conecta dos nodos que ya pertenecían a la misma componente: un caso clásico de detección de ciclos con DSU.
# Example
# n=5, edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
# Adding edge [2,3] creates cycle 1-2-3-1
# So [2,3] is the redundant connection
# Key insight: process edges one by one with DSU
# The FIRST edge where both endpoints are already connected is the redundant one
print('Tree property: n nodes, n-1 edges, no cycles')
print('Adding 1 edge: n nodes, n edges, exactly 1 cycle')
print('DSU approach: find the edge that connects already-connected nodes')Detección de ciclos con DSU
DSU detecta ciclos de forma natural: antes de añadir una arista (u, v), compruebe si find(u) == find(v). Si comparten raíz, ya están conectados; añadir esta arista crea un ciclo. Esta es la arista redundante.
Este enfoque funciona para grafos no dirigidos. Para cada arista, unimos correctamente las dos componentes (todavía no hay ciclo) o detectamos que ambos extremos ya están en la misma componente (se ha encontrado un ciclo). La complejidad temporal es O(n × alpha(n)), prácticamente O(n).
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1)) # 1-indexed
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # same component => cycle found
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
edges = [[1,2],[1,3],[2,3],[2,4],[3,5]]
print(find_redundant_connection(edges)) # [2, 3]Seguimiento paso a paso del algoritmo
Sigamos [[1,2],[1,3],[2,3]] paso a paso. Inicialmente, cada nodo es su propia componente: {1}, {2}, {3}.
- Arista [1,2]: find(1)=1, find(2)=2, son diferentes; las unimos. Componentes: {1,2}, {3}
- Arista [1,3]: find(1)=root, find(3)=3, son diferentes; las unimos. Componentes: {1,2,3}
- Arista [2,3]: find(2)=root, find(3)=root; ¡misma raíz! Se ha detectado un ciclo. Devuelva [2,3].
El algoritmo procesa las aristas en orden y devuelve la primera arista que completa un ciclo. Como el problema garantiza que solo existe una arista adicional, esta siempre es la arista redundante correcta.
def find_redundant_trace(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
print(f'Edge ({u},{v}): find({u})={pu}, find({v})={pv}', end=' => ')
if pu == pv:
print('CYCLE DETECTED!')
return [u, v]
parent[pv] = pu
print('merged')
return []
result = find_redundant_trace([[1,2],[1,3],[2,3]])
print('Redundant edge:', result)Detección de ciclos en grafos no dirigidos con DFS
Una alternativa a DSU para detectar ciclos en grafos no dirigidos es DFS con seguimiento del padre. Durante DFS, si llegamos a un nodo que ya ha sido visitado y no es el padre directo del nodo actual, hemos encontrado una arista de retorno, lo que indica un ciclo.
Sin embargo, el enfoque con DFS requiere un tiempo O(V + E) y devuelve si existe un ciclo, pero no indica fácilmente qué arista concreta es redundante. Se prefiere DSU en los problemas que piden identificar la arista redundante específica, porque esta se encuentra de forma natural cuando falla la unión.
from collections import defaultdict
def has_cycle_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb == parent:
continue # skip the edge we came from
if nb in visited:
return True # back edge => cycle
if dfs(nb, node):
return True
return False
for node in range(1, n + 1):
if node not in visited:
if dfs(node, -1):
return True
return False
print(has_cycle_dfs(3, [[1,2],[1,3],[2,3]])) # True
print(has_cycle_dfs(3, [[1,2],[1,3]])) # FalseDetección de ciclos en grafos dirigidos
Para los grafos dirigidos, la detección de ciclos con DSU no funciona directamente porque las aristas tienen dirección. En su lugar, utilice DFS con marcado de tres colores: blanco (no visitado), gris (en el camino DFS actual) y negro (procesado por completo). Una arista de retorno a un nodo gris indica un ciclo.
En un grafo no dirigido, cualquier arista de retorno implica un ciclo. En un grafo dirigido, una arista transversal hacia un nodo negro no forma un ciclo; solo lo hacen las aristas de retorno hacia nodos grises. Esta distinción es fundamental y se evalúa en los problemas de planificación de cursos.
def has_cycle_directed(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0=white(unvisited), 1=grey(in stack), 2=black(done)
color = [0] * (n + 1)
def dfs(node):
color[node] = 1 # grey: currently visiting
for nb in graph[node]:
if color[nb] == 1:
return True # back edge to grey node => cycle
if color[nb] == 0:
if dfs(nb):
return True
color[node] = 2 # black: fully processed
return False
for node in range(1, n + 1):
if color[node] == 0:
if dfs(node):
return True
return False
from collections import defaultdict
print(has_cycle_directed(3, [[1,2],[2,3],[3,1]])) # True: 1->2->3->1
print(has_cycle_directed(3, [[1,2],[1,3],[2,3]])) # FalseConexión redundante II: variante para grafos dirigidos
LeetCode 685 amplía el problema a grafos dirigidos en los que cada nodo tiene exactamente un padre (forman un árbol enraizado con una arista adicional). Se presentan dos casos: un nodo tiene dos padres (grado de entrada 2) o existe un ciclo sin que ningún nodo tenga dos padres.
La solución busca primero nodos con grado de entrada 2. Si encuentra uno, una de sus dos aristas entrantes debe ser la respuesta. A continuación, la detección de ciclos con DSU determina cuál de las dos aristas candidatas se debe eliminar. Este enfoque en dos fases gestiona correctamente todos los casos.
def find_redundant_directed(edges):
n = len(edges)
parent_map = {} # node -> its parent in the input
candidate1 = candidate2 = None
for u, v in edges:
if v in parent_map: # v already has a parent
candidate1 = [parent_map[v], v] # earlier edge
candidate2 = [u, v] # later edge
else:
parent_map[v] = u
# DSU cycle detection, skipping candidate2 if it exists
dsu = list(range(n + 1))
def find(x):
while dsu[x] != x: dsu[x] = dsu[dsu[x]]; x = dsu[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
dsu[px] = py; return True
for u, v in edges:
if candidate2 and [u, v] == candidate2: continue # skip candidate2
if not union(u, v): # cycle found without candidate2
return candidate1 if candidate1 else [u, v]
return candidate2 # no cycle when excluding candidate2 => candidate2 is redundant
print(find_redundant_directed([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_directed([[1,2],[2,3],[3,4],[4,1],[1,5]])) # [4,1]Validez del grafo después de eliminar una arista
Después de identificar la arista redundante, podemos verificar el resultado comprobando que, al eliminarla, queda un árbol válido: exactamente n-1 aristas, todos los nodos conectados y ningún ciclo. Para los fines del problema de entrevista, DSU lo garantiza de forma natural: si devolvemos la arista cuya unión falló, al eliminarla quedan exactamente las n-1 aristas cuyas uniones se realizaron correctamente, y estas forman un árbol de expansión.
Esta garantía explica por qué DSU resulta tan sencillo para este problema: las uniones correctas construyen el árbol progresivamente y la unión fallida identifica la única arista que no pertenece a él.
def verify_tree(n, edges, removed_edge):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
components = n
for u, v in edges:
if [u, v] == removed_edge:
continue # skip the removed edge
pu, pv = find(u), find(v)
if pu == pv:
print('CYCLE DETECTED after removal! Wrong answer.')
return False
parent[pv] = pu
components -= 1
if components != 1:
print(f'Graph not connected ({components} components). Wrong answer.')
return False
print('Valid tree after removing edge:', removed_edge)
return True
edges = [[1,2],[1,3],[2,3]]
verify_tree(3, edges, [2,3])
verify_tree(3, edges, [1,2]) # wrong removalAnálisis de la complejidad temporal y espacial
La solución de conexión redundante basada en DSU procesa cada una de las n aristas exactamente una vez, y cada operación de union/find tiene un coste amortizado de O(alpha(n)). Tiempo total: O(n × alpha(n)), efectivamente O(n).
La complejidad espacial es O(n) para los arrays de padres y rangos. Esto es óptimo: como mínimo, debe leer las n aristas y almacenar algún estado por nodo. Compárelo con un enfoque ingenuo que ejecuta DFS después de insertar cada arista: O(n²) de tiempo y O(n + E) de espacio.
# Summary of complexities
complexity = {
'Naive (DFS after each edge)': {'time': 'O(n^2)', 'space': 'O(n)'},
'DSU (path compression + rank)': {'time': 'O(n * alpha(n))', 'space': 'O(n)'},
'Sorting + DSU (Kruskal style)': {'time': 'O(n log n)', 'space': 'O(n)'},
}
for approach, costs in complexity.items():
print(f'{approach}:')
print(f' Time: {costs["time"]}')
print(f' Space: {costs["space"]}')
print()
print('alpha(n) <= 4 for all practical n, so DSU is effectively O(n).')Caso límite: bucle sobre sí mismo
Una arista que forma un bucle sobre sí misma [u, u] crea inmediatamente un ciclo, ya que ambos extremos son el mismo nodo. En DSU, find(u) == find(u) siempre es verdadero, por lo que la unión falla de inmediato y [u, u] se devuelve como la arista redundante.
La mayoría de las restricciones de los problemas garantizan que no haya bucles sobre sí mismos, pero el código robusto debe gestionarlos. La implementación de DSU los gestiona de forma natural, sin ningún caso especial: la comprobación de ciclos if find(u) == find(v) los detecta antes de intentar realizar la unión. Verifique siempre el comportamiento con entradas de casos límite, como bucles en un único nodo y entradas del tamaño mínimo.
def find_redundant_robust(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
return [u, v] # handles self-loops too: u==v => pu==pv always
parent[pv] = pu
return []
# Self-loop test
print(find_redundant_robust([[1,2],[2,2]])) # [2,2] self-loop
# Minimum tree test
print(find_redundant_robust([[1,2],[2,3],[1,3]])) # [1,3]
# Standard test
print(find_redundant_robust([[1,2],[1,3],[2,3],[2,4],[3,5]])) # [2,3]Generalización de la detección de ciclos entre algoritmos
Existen varios algoritmos para detectar ciclos, cada uno adecuado para situaciones diferentes:
- DSU: grafos no dirigidos, llegada de aristas en línea, O(alpha(n)) por arista; es la mejor opción para contar ciclos o encontrar la arista redundante
- DFS con seguimiento del padre: grafos no dirigidos, todas las aristas conocidas por adelantado, O(V+E); es la mejor opción cuando necesita el camino del ciclo
- DFS de tres colores: grafos dirigidos, detección de aristas de retorno, O(V+E); es la mejor opción para la planificación de cursos y la ordenación topológica
- Ordenación topológica (Kahn): grafos dirigidos, detecta ciclos mediante los nodos restantes con grado de entrada distinto de cero; es la mejor opción cuando también necesita obtener un orden
# When to use which cycle-detection method:
# Problem type => preferred algorithm
problems = [
('Redundant Connection (undirected)', 'DSU'),
('Course Schedule (directed)', 'DFS three-color or Kahn topological sort'),
('Detect cycle in undirected graph', 'DFS with parent tracking or DSU'),
('Find cycle members in directed graph', 'DFS three-color + backtrack'),
('Online graph edges with cycle check', 'DSU'),
('Minimum spanning tree validity', 'DSU (Kruskal)'),
]
for problem, solution in problems:
print(f'{problem}\n => {solution}\n')Solución completa con casos límite
A continuación se muestra una solución de calidad de producción para Conexión redundante que gestiona todos los casos límite: nodos indexados desde 1, exactamente una arista redundante y la garantía de que eliminarla deja un árbol válido. Utiliza el DSU óptimo con reducción a la mitad de caminos y unión por rango.
Después de enviarla, intente resolver la siguiente variante: ¿qué ocurriría si el grafo pudiera tener varias aristas redundantes? Tendría que registrar todas las aristas que completan un ciclo y devolver la última de la entrada; la misma estrategia voraz seguiría funcionando porque DSU procesa las aristas en orden.
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v]
return [] # should never reach here given valid input
test_cases = [
[[1,2],[1,3],[2,3]],
[[1,2],[2,3],[3,4],[1,4],[1,5]],
[[1,2],[1,3],[2,3],[2,4],[3,5]],
]
for tc in test_cases:
print(find_redundant_connection(tc))Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: una conexión redundante es una arista que conecta dos nodos que ya estaban conectados en un grafo no dirigido, DSU la detecta comprobando find(u) == find(v) antes de realizar la unión y devolviendo esa arista, y los grafos dirigidos requieren DFS de tres colores o el algoritmo de Kahn en lugar de DSU para detectar ciclos. A continuación, aplicaremos DSU al problema de combinación de cuentas, donde los correos electrónicos son los nodos y los correos compartidos entre cuentas activan las uniones.
Preguntas frecuentes
¿La lección «Conexión redundante y detección de ciclos» es gratis?
Sí — el texto completo de «Conexión redundante y detección de ciclos» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Conexión redundante y detección de ciclos»?
Detecte la arista que crea un ciclo en un grafo no dirigido aplicando union a cada arista y comprobando si dos nodos ya están conectados. Practicas DSA Interview Prep 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 DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep 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 «Conexión redundante y detección de ciclos»?
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 DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep 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
- DSU con compresión de caminos
- Unión por rango y cota de Ackermann inversa
- Conexión redundante y detección de ciclos
- Fusión de cuentas y componentes conexas