Redundant Connection
Una rete è iniziata come un albero: n nodi, numerati da 1 a n, collegati da n-1 archi non orientati e senza cicli. Poi è stato aggiunto un altro arco tra due nodi che non erano collegati direttamente, quindi la lista edges contiene ora n archi e un solo ciclo.
Restituisci un arco che puoi rimuovere in modo che gli altri n-1 archi formino di nuovo un albero. Se ci sono più archi validi, restituisci quello che compare più avanti in edges, come coppia [a, b] esattamente come è scritta lì.
Funzione
- edgesinteger-2d-array
- gli n archi non orientati, ciascuno una coppia [a, b] di nodi numerati a partire da 1
- Restituisceinteger-array
- l'arco del ciclo che compare per ultimo in edges, scritto così com'è lì
Vincoli
3 ≤ n ≤ 5000, doven = edges.lengthedges[i] = [a, b]con1 ≤ a, b ≤ nea ≠ b- Nessun arco compare due volte, in nessuna delle due direzioni.
- The edge collegano tutti i
nnodi e contengono esattamente un ciclo.
Esempi
- Input
- edges = [[1, 2], [1, 3], [2, 3]]
- Output
- [2, 3]
- Spiegazione
- I tre lati formano il triangolo 1, 2, 3, quindi rimuovendone uno qualsiasi si ottiene un albero.
[2, 3]è l'ultimo elemento dell'elenco.
- Input
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Output
- [1, 4]
- Spiegazione
- Il ciclo è 1, 2, 3, 4, 1. L'arco
[1, 5]non ne fa parte: rimuovendolo, il nodo 5 rimarrebbe isolato. Tra i quattro archi del ciclo,[1, 4]compare per ultimo.
Per approfondire
Se gli archi fossero orientati e il grafo originale fosse un albero radicato, quale arco rimuoveresti quando l'arco aggiuntivo fa sì che un nodo abbia due genitori?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Rimuovendo l'arco, tutti i nodi
ndevono rimanere connessi. Quali archi puoi togliere senza dividere il grafo in due?Solo gli archi del ciclo: ognuno ha un secondo percorso intorno al ciclo, mentre ogni altro arco è l’unico collegamento con una parte del grafo. Quindi la risposta è l’arco del ciclo che compare per ultimo nell’elenco.
Aggiungi gli archi, nell'ordine dell'elenco, a
ngruppi separati. Il primo arco i cui due estremi si trovano già nello stesso gruppo chiude il ciclo, e tutti gli altri archi del ciclo lo precedono. Una struttura union-find trova quell'arco in un solo passaggio.
Soluzione
Rimuovere un arco lascia un albero esattamente quando l'arco si trova sull'unico ciclo del grafo, quindi la risposta è l'arco del ciclo che compare per ultimo nell'elenco. Union-find lo individua in un solo passaggio: aggiungi gli archi nell'ordine e il primo arco i cui estremi sono già connessi è la risposta.
Prova a rimuovere ogni bordo, iniziando dall’ultimo
Corretto, ma non termina sui test più grandi
Intuizione
Rimuovi un arco e verifica se gli altri n-1 archi formano un albero. Con n nodi e n-1 archi, lo formano esattamente quando una ricerca dal nodo 1 raggiunge tutti gli n nodi. Prova gli archi partendo dalla fine dell’elenco, così la prima rimozione che supera la verifica è quella più recente. Memorizza l’indice di ciascun arco nelle liste di adiacenza e una ricerca può saltare l’arco rimosso senza ricostruire nulla.
Ogni tentativo è una ricerca completa O(n) e i tentativi possono essere n: fino a 2.5 × 10^7 passi quando n = 5000.
Algoritmo
- Costruisci liste di adiacenza che mantengano, per ogni nodo vicino, l’indice dell’arco che conduce a esso.
- Per
skip, partendo dall’ultimo indice e procedendo fino a 0, cerca dal nodo 1 e ignora l’arco con indiceskip. - Conta i nodi raggiunti dalla ricerca.
- Se raggiunge tutti gli
n, restituisciedges[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 []Sbuccia le foglie
Intuizione
Una foglia, un nodo con un solo arco, non può trovarsi su un ciclo, perché un ciclo entra ed esce da ciascuno dei suoi nodi. Rimuovere una foglia può trasformare il suo vicino in una foglia, quindi continua a eliminarle finché non ne rimane nessuna. Ciò che resta è esattamente il ciclo, poiché ogni nodo del ciclo conserva i suoi due archi del ciclo. Nel secondo esempio il nodo 5 viene eliminato, il nodo 1 mantiene due archi e rimangono i nodi da 1 a 4.
Qualsiasi arco tra due nodi rimanenti è un arco del ciclo, perché un secondo collegamento tra nodi del ciclo creerebbe un secondo ciclo. Quindi esamina edges dalla fine e restituisci il primo arco i cui estremi sono entrambi ancora presenti.
Algoritmo
- Crea le liste di adiacenza e conta il grado di ogni nodo.
- Inserisci in uno stack ogni nodo di grado 1.
- Estrai una foglia, imposta il suo grado a 0 e diminuisci il grado del suo vicino rimanente; inserisci quel vicino quando il suo grado scende a 1.
- Quando lo stack è vuoto, i nodi con grado superiore a 0 formano il ciclo.
- Esamina
edgesa partire dalla fine e restituisci il primo arco i cui estremi sono entrambi ancora presenti.
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: il primo arco che chiude un ciclo
Intuizione
Aggiungi gli archi nell'ordine della lista e tieni traccia dei nodi connessi. Finché il ciclo non si chiude, ogni arco unisce due componenti senza alcun percorso tra loro. Il primo arco i cui estremi sono già connessi chiude il ciclo. Gli altri archi del ciclo sono stati aggiunti prima, quindi è l'arco del ciclo che compare per ultimo. Nel secondo esempio [1, 4] trova i nodi 1 e 4 già uniti, e [1, 5] non viene mai letto.
La struttura union-find mantiene un array, parent; seguendo i puntatori da un nodo si arriva alla radice della sua componente. Collegare la componente più piccola sotto quella più grande e puntare i nodi ai loro nonni durante find mantiene corte le catene. Ogni operazione ha quindi un costo ammortizzato O(α(n)), dove α, la funzione inversa di Ackermann, è al massimo 4 per qualsiasi input reale.
Algoritmo
- Punta ogni nodo da 1 a
na sé stesso,parent[x] = x, e assegnagli dimensione 1. - Scorri
edgesin ordine. Per[u, v], cerca la radice diue la radice div. - Se le radici coincidono,
[u, v]chiude il ciclo: restituiscilo così com'è. - Altrimenti, il gruppo più grande assorbe quello più piccolo: la sua radice diventa il genitore della radice più piccola e le dimensioni si sommano.
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 []
Trappole e casi limite
- Restituire l'ultimo arco della lista. Nel secondo esempio è
[1, 5], e rimuoverlo taglia fuori il nodo 5. - Scansionare dall'inizio dopo aver eliminato gli archi. Questo restituisce il primo arco del ciclo,
[1, 2]nel secondo esempio. - Ordinare o invertire la coppia. Se la lista contiene
[3, 1], restituisci[3, 1], non[1, 3]. - Dimensionare gli array per i nodi da 0 a
n-1. I nodi sono numerati a partire da 1, quindi il nodonrichiede un array din+1elementi. - Ricorrere lungo il ciclo. Può passare attraverso tutti i 5000 nodi, cinque volte il limite predefinito di ricorsione di Python, quindi usa uno stack esplicito e un ciclo in
find.
Domande frequenti3
Qual è la complessità temporale di Redundant Connection?
Union-find risolve il problema in un solo passaggio sugli n archi: tempo O(n · α(n)), dove α(n) è al massimo 4 nella pratica, e spazio O(n). Anche l’eliminazione delle foglie è O(n). Provare ogni rimozione con una nuova ricerca costa O(n²).
Quali archi si possono rimuovere per lasciare un albero?
Esattamente gli archi del ciclo. Ognuno di essi ha un secondo percorso tra i suoi estremi, attraverso il resto del ciclo, quindi rimuoverlo mantiene il grafo connesso. Qualsiasi altro arco è l'unico collegamento tra due parti del grafo e rimuoverlo le separa.
È possibile risolvere Redundant Connection con DFS?
Sì. Prima di aggiungere ogni arco, cerca da un’estremità lungo gli archi aggiunti finora; il primo arco la cui altra estremità è già raggiungibile è la risposta. Questo richiede O(n) per arco, O(n²) in totale, mentre union-find risponde alla stessa domanda in un tempo pressoché costante.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def findRedundantConnection(edges):
# Scrivi il codice quiTest #1
Test #2
Argomento
edges = [[1, 2], [1, 3], [2, 3]]
Output atteso
[2, 3]