Redundant Connection
Una red comenzó como un árbol: n nodos, numerados del 1 al n, unidos por n-1 aristas no dirigidas sin ciclos. Después se añadió una arista más entre dos nodos que no estaban unidos directamente, así que la lista edges ahora contiene n aristas y exactamente un ciclo.
Devuelve una arista que puedas eliminar para que las otras n-1 aristas vuelvan a formar un árbol. Si hay varias aristas que sirven, devuelve la que aparece en último lugar en edges, como el par [a, b] exactamente tal como está escrito allí.
Función
- edgesinteger-2d-array
- las n aristas no dirigidas, cada una un par [a, b] de nodos numerados del 1
- Devuelveinteger-array
- la arista del ciclo que aparece al final en edges, escrita tal como aparece allí
Restricciones
3 ≤ n ≤ 5000, donden = edges.lengthedges[i] = [a, b]con1 ≤ a, b ≤ nya ≠ b- No aparece ninguna arista dos veces, en ninguna dirección.
- Las aristas conectan los
nnodos y contienen exactamente un ciclo.
Ejemplos
- Entrada
- edges = [[1, 2], [1, 3], [2, 3]]
- Salida
- [2, 3]
- Explicación
- Las tres aristas forman el triángulo 1, 2, 3, así que quitar cualquiera de ellas deja un árbol.
[2, 3]aparece al final de la lista.
- Entrada
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Salida
- [1, 4]
- Explicación
- El ciclo es 1, 2, 3, 4, 1. La arista
[1, 5]no forma parte de él: eliminarla dejaría aislado el nodo 5. De las cuatro aristas del ciclo,[1, 4]aparece al final.
Para ir más allá
Si las aristas estuvieran dirigidas y el grafo original fuera un árbol enraizado, ¿qué arista eliminarías cuando la arista adicional le da a un nodo dos padres?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Al eliminar la arista, todos los nodos
ndeben quedar conectados. ¿Qué aristas puedes quitar sin dividir el grafo en dos?Solo las aristas del ciclo: cada una tiene una segunda ruta alrededor del ciclo, y todas las demás aristas son el único enlace a alguna parte del grafo. Así que la respuesta es la arista del ciclo que aparece al final de la lista.
Agrega las aristas en el orden de la lista a
ngrupos separados. La primera arista cuyos dos extremos ya están en el mismo grupo cierra el ciclo, y todas las demás aristas del ciclo aparecieron antes. Una estructura union-find encuentra esa arista en una sola pasada.
Solución
Eliminar una arista deja un árbol exactamente cuando la arista está en el único ciclo del grafo, así que la respuesta es la arista del ciclo que aparece al final de la lista. Union-find la encuentra en una sola pasada: añade las aristas en orden, y la primera arista cuyos extremos ya están conectados es la respuesta.
Prueba a eliminar cada arista, empezando por la última
Correcto, pero no termina con las pruebas más grandes
Intuición
Quita una arista y comprueba si las otras n-1 aristas forman un árbol. Con n nodos y n-1 aristas, esto se cumple exactamente cuando una búsqueda desde el nodo 1 llega a los n nodos. Prueba las aristas desde el final de la lista, así que la primera eliminación que funciona es la más reciente. Guarda el índice de cada arista en las listas de adyacencia, y una búsqueda puede saltarse la arista eliminada sin reconstruir nada.
Cada intento es una búsqueda completa de O(n), y puede haber n intentos: hasta 2.5 × 10^7 pasos cuando n = 5000.
Algoritmo
- Construye listas de adyacencia que mantengan, para cada vecino, el índice de la arista que lleva hasta él.
- Para
skip, desde el último índice hasta 0, busca desde el nodo 1 e ignora la arista con índiceskip. - Cuenta los nodos a los que llega la búsqueda.
- Si llega a todos los
n, devuelveedges[skip].
def findRedundantConnection(edges):
n = len(edges)
# graph[x] holds (neighbour, index of the edge) for every edge at node x.
graph = [[] for _ in range(n + 1)]
for i, (u, v) in enumerate(edges):
graph[u].append((v, i))
graph[v].append((u, i))
# Try leaving out each edge, the last one first.
for skip in range(n - 1, -1, -1):
# Without edge skip, can node 1 still reach all n nodes?
seen = [False] * (n + 1)
seen[1] = True
stack = [1]
reached = 1
while stack:
node = stack.pop()
for nxt, i in graph[node]:
if i != skip and not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
# n-1 edges that connect n nodes form a tree.
if reached == n:
return edges[skip]
return []Quita las hojas
Intuición
Una hoja, un nodo con una sola arista, no puede estar en un ciclo, porque un ciclo entra y sale de cada uno de sus nodos. Quitar una hoja puede convertir a su vecino en una hoja, así que sigue quitándolas hasta que no quede ninguna. Lo que queda es exactamente el ciclo, ya que cada nodo del ciclo conserva sus dos aristas del ciclo. En el segundo ejemplo, se quita el nodo 5, el nodo 1 conserva dos aristas y quedan los nodos del 1 al 4.
Cualquier arista entre dos nodos restantes pertenece a un ciclo, porque un segundo enlace entre nodos del ciclo formaría un segundo ciclo. Así que recorre edges desde el final y devuelve la primera arista cuyos extremos sigan estando.
Algoritmo
- Construye listas de adyacencia y cuenta el grado de cada nodo.
- Apila todos los nodos de grado 1.
- Desapila una hoja, establece su grado en 0 y reduce el grado de su vecino restante; apila ese vecino cuando su grado baje a 1.
- Cuando la pila esté vacía, los nodos con un grado superior a 0 forman el ciclo.
- Recorre
edgesdesde el final y devuelve la primera arista cuyos dos extremos sigan presentes.
def findRedundantConnection(edges):
n = len(edges)
graph = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
# A node with one edge cannot lie on the cycle. Remove it, and repeat.
stack = [x for x in range(1, n + 1) if degree[x] == 1]
while stack:
leaf = stack.pop()
degree[leaf] = 0
for nxt in graph[leaf]:
if degree[nxt] > 0:
degree[nxt] -= 1
if degree[nxt] == 1:
stack.append(nxt)
# Only the cycle is left. Its edge that comes last in the list is the answer.
for u, v in reversed(edges):
if degree[u] > 0 and degree[v] > 0:
return [u, v]
return []Union-find: la primera arista que cierra un ciclo
Intuición
Añade las aristas en el orden de la lista y lleva un registro de qué nodos están conectados. Hasta que se cierre el ciclo, cada arista une dos componentes sin ningún camino entre ellas. La primera arista cuyos extremos ya están conectados cierra el ciclo. Las demás aristas del ciclo se añadieron antes, así que la arista que cierra el ciclo es la última que aparece. En el segundo ejemplo, [1, 4] encuentra que los nodos 1 y 4 ya están conectados, y [1, 5] nunca se lee.
La estructura union-find mantiene un array, parent; al seguir los punteros desde un nodo, se llega a la raíz de su componente. Colocar la componente más pequeña debajo de la más grande y hacer que los nodos apunten a sus abuelos durante find mantiene cortas las cadenas. Cada operación cuesta entonces O(α(n)) amortizado, donde α, la función inversa de Ackermann, es como máximo 4 para cualquier entrada real.
Algoritmo
- Haz que cada nodo del 1 al
napunte a sí mismo,parent[x] = x, y asígnale tamaño 1. - Recorre
edgesen orden. Para[u, v], busca la raíz deuy la raíz dev. - Si las raíces coinciden,
[u, v]cierra el ciclo: devuélvelo tal como está escrito. - Si no, el componente más grande absorbe al más pequeño: su raíz se convierte en el padre de la raíz más pequeña y se suman los tamaños.
def findRedundantConnection(edges):
n = len(edges)
parent = list(range(n + 1)) # every node starts as its own group
size = [1] * (n + 1)
def find(x):
# Walk up to the root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
# u and v are already connected: this edge closes the cycle.
if a == b:
return [u, v]
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return []
Errores comunes y casos límite
- Devolver la última arista de la lista. En el segundo ejemplo, es
[1, 5], y al eliminarla se separa el nodo 5. - Recorrer desde el principio después de quitar las hojas. Eso devuelve la primera arista del ciclo,
[1, 2]en el segundo ejemplo. - Ordenar o invertir el par. Si la lista contiene
[3, 1], devuelve[3, 1], no[1, 3]. - Dimensionar los arreglos para los nodos de 0 a
n-1. Los nodos se numeran desde 1, así que el nodonnecesita un arreglo den+1posiciones. - Usar recursión alrededor del ciclo. Puede recorrer los 5000 nodos, cinco veces el límite de recursión predeterminado de Python, así que usa una pila explícita y un bucle en
find.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Redundant Connection?
Union-find lo resuelve en una sola pasada por las n aristas: tiempo O(n · α(n)), donde α(n) es como máximo 4 en la práctica, y espacio O(n). Eliminar las hojas también tiene un costo de O(n). Probar cada eliminación con una búsqueda nueva cuesta O(n²).
¿Qué aristas se pueden eliminar para dejar un árbol?
Exactamente las aristas del ciclo. Cada una de ellas tiene una segunda ruta entre sus extremos a través del resto del ciclo, así que eliminarla mantiene el grafo conectado. Cualquier otra arista es el único enlace entre dos partes del grafo, y eliminarla las separa.
¿Se puede resolver Conexión redundante con DFS?
Sí. Antes de añadir cada arista, busca desde un extremo recorriendo las aristas añadidas hasta ese momento; la primera arista cuyo otro extremo ya sea alcanzable es la respuesta. Eso cuesta O(n) por arista, O(n²) en total, mientras que union-find responde a la misma pregunta en tiempo casi constante.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def findRedundantConnection(edges):
# Escribe el código aquíPrueba #1
Prueba #2
Argumento
edges = [[1, 2], [1, 3], [2, 3]]
Salida Esperada
[2, 3]