Redundant Connection
Uma rede começou como uma árvore: n nós, numerados de 1 a n, conectados por n-1 arestas não direcionadas, sem ciclos. Em seguida, foi adicionada mais uma aresta entre dois nós que não estavam conectados diretamente, então a lista edges agora contém n arestas e exatamente um ciclo.
Retorne uma aresta que você possa remover para que as outras n-1 arestas formem novamente uma árvore. Se várias arestas servirem, retorne a que aparece por último em edges, como o par [a, b], exatamente como está escrito ali.
Função
- edgesinteger-2d-array
- as n arestas não direcionadas, cada uma um par [a, b] de nós numerados a partir de 1
- Retornainteger-array
- o arco do ciclo que aparece por último em edges, escrito exatamente como está lá
Restrições
3 ≤ n ≤ 5000, em quen = edges.lengthedges[i] = [a, b]com1 ≤ a, b ≤ nea ≠ b- Nenhuma aresta aparece duas vezes, em nenhuma das direções.
- As arestas conectam todos os
nnós e contêm exatamente um ciclo.
Exemplos
- Entrada
- edges = [[1, 2], [1, 3], [2, 3]]
- Saída
- [2, 3]
- Explicação
- As três arestas formam o triângulo 1, 2, 3, então remover qualquer uma delas deixa uma árvore.
[2, 3]vem por último na lista.
- Entrada
- edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
- Saída
- [1, 4]
- Explicação
- O ciclo é 1, 2, 3, 4, 1. A aresta
[1, 5]não faz parte dele: removê-la isolaria o nó 5. Das quatro arestas do ciclo,[1, 4]aparece por último.
Para ir além
Se as arestas fossem direcionadas e o grafo original fosse uma árvore enraizada, qual aresta você removeria quando a aresta extra dá a um nó dois pais?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Remover a aresta deve deixar todos os
nnós conectados. Quais arestas você pode remover sem dividir o grafo em dois?Apenas as arestas do ciclo: cada uma tem uma segunda rota ao longo do ciclo, e todas as outras arestas são a única ligação com alguma parte do grafo. Portanto, a resposta é a aresta do ciclo que aparece por último na lista.
Adicione as arestas, na ordem da lista, a
ngrupos separados. A primeira aresta cujas duas extremidades já estão no mesmo grupo fecha o ciclo, e todas as outras arestas do ciclo vieram antes dela. Uma estrutura union-find encontra essa aresta em uma única passagem.
Solução
Remover uma aresta deixa uma árvore exatamente quando a aresta está no único ciclo do grafo; portanto, a resposta é a aresta do ciclo que aparece por último na lista. A estrutura union-find a encontra em uma única passagem: adicione as arestas em ordem, e a primeira aresta cujas extremidades já estão conectadas é a resposta.
Tente remover cada aresta, começando pela última
Correta, mas não termina nos maiores testes
Intuição
Remova uma aresta e verifique se as outras n-1 arestas formam uma árvore. Com n nós e n-1 arestas, isso acontece exatamente quando uma busca a partir do nó 1 alcança todos os n nós. Tente as arestas do fim da lista para o início, assim a primeira remoção que funcionar será a mais recente. Armazene o índice de cada aresta nas listas de adjacência, e uma busca pode ignorar a aresta removida sem reconstruir nada.
Cada tentativa é uma busca completa de O(n), e pode haver n tentativas: até 2.5 × 10^7 passos quando n = 5000.
Algoritmo
- Crie listas de adjacência que mantenham, para cada vizinho, o índice da aresta que leva até ele.
- Para
skip, do último índice até 0, faça uma busca a partir do nó 1 e ignore a aresta com índiceskip. - Conte os nós alcançados pela busca.
- Se ela alcançar todos os
n, retorneedges[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 []Retire as folhas
Intuição
Uma folha, um nó com uma aresta, não pode estar em um ciclo, porque um ciclo entra e sai de cada um de seus nós. Remover uma folha pode transformar seu vizinho em uma folha, então continue removendo folhas até que não reste nenhuma. O que resta é exatamente o ciclo, pois cada nó do ciclo mantém suas duas arestas do ciclo. No segundo exemplo, o nó 5 é removido, o nó 1 mantém duas arestas, e os nós de 1 a 4 permanecem.
Qualquer aresta entre dois nós restantes é uma aresta do ciclo, porque uma segunda ligação entre nós do ciclo criaria um segundo ciclo. Então percorra edges de trás para frente e retorne a primeira aresta cujas extremidades permaneçam.
Algoritmo
- Construa listas de adjacência e conte o grau de cada nó.
- Empilhe todos os nós de grau 1.
- Desempilhe uma folha, defina seu grau como 0 e diminua o grau do vizinho restante; empilhe esse vizinho quando seu grau cair para 1.
- Quando a pilha estiver vazia, os nós com grau maior que 0 formarão o ciclo.
- Percorra
edgesde trás para frente e retorne a primeira aresta cujas duas extremidades ainda permaneçam.
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: a primeira aresta que fecha um ciclo
Intuição
Adicione as arestas na ordem da lista e acompanhe quais nós estão conectados. Até que o ciclo se feche, cada aresta une duas partes sem nenhum caminho entre elas. A primeira aresta cujas extremidades já estão conectadas fecha o ciclo. As outras arestas do ciclo foram adicionadas antes dela, então essa é a aresta do ciclo que aparece por último. No segundo exemplo, [1, 4] encontra os nós 1 e 4 já unidos, e [1, 5] nunca é lido.
A estrutura union-find mantém um array, parent; seguir os ponteiros a partir de um nó leva à raiz de sua parte. Anexar a parte menor sob a maior e apontar os nós para seus avós durante find mantém as cadeias curtas. Cada operação custa, então, O(α(n)) amortizado, em que α, a função inversa de Ackermann, é no máximo 4 para qualquer entrada real.
Algoritmo
- Aponte cada nó de 1 a
npara si mesmo,parent[x] = x, e atribua a ele o tamanho 1. - Percorra
edgesem ordem. Para[u, v], procure a raiz deue a raiz dev. - Se as raízes forem iguais,
[u, v]fecha o ciclo: retorne-o como está escrito. - Caso contrário, o componente maior absorve o menor: sua raiz se torna o pai da raiz menor, e os tamanhos são somados.
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 []
Armadilhas e casos extremos
- Retornar a última aresta da lista. No segundo exemplo, ela é
[1, 5], e removê-la desconecta o nó 5. - Percorrer a lista a partir do início depois de remover arestas. Isso retorna a aresta mais antiga do ciclo,
[1, 2]no segundo exemplo. - Ordenar ou inverter o par. Se a lista contiver
[3, 1], retorne[3, 1], não[1, 3]. - Dimensionar arrays para os nós de 0 a
n-1. Os nós são numerados a partir de 1, então o nónprecisa de um array comn+1posições. - Usar recursão ao percorrer o ciclo. Ela pode passar por todos os 5000 nós, cinco vezes o limite padrão de recursão do Python, então use uma pilha explícita e um loop em
find.
Perguntas frequentes3
Qual é a complexidade de tempo de Redundant Connection?
Union-find resolve isso em uma única passagem pelas n arestas: tempo O(n · α(n)), em que α(n) é no máximo 4 na prática, e espaço O(n). Remover as folhas também custa O(n). Tentar cada remoção com uma nova busca custa O(n²).
Quais arestas podem ser removidas para deixar uma árvore?
Exatamente as arestas do ciclo. Cada uma delas tem uma segunda rota entre suas extremidades pelo restante do ciclo, então removê-la mantém o grafo conectado. Qualquer outra aresta é a única ligação entre duas partes do grafo, e removê-la as separa.
É possível resolver Redundant Connection com DFS?
Sim. Antes de adicionar cada aresta, pesquise a partir de uma das extremidades pelas arestas adicionadas até então; a primeira aresta cuja outra extremidade já seja alcançável é a resposta. Isso custa O(n) por aresta, O(n²) no total, enquanto a estrutura union-find responde à mesma pergunta em tempo quase constante.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def findRedundantConnection(edges):
# Escreva o código aquiTeste #1
Teste #2
Argumento
edges = [[1, 2], [1, 3], [2, 3]]
Saída Esperada
[2, 3]