Graph Valid Tree

Q: Qual é a complexidade de tempo de Graph Valid Tree?

O(n + m) com uma busca em profundidade, em que m é o número de arestas, e O(n + m α(n)) com union-find. Ambos verificam primeiro a quantidade de arestas, então um grafo com uma quantidade incorreta é rejeitado antes de qualquer busca.

MédioUnion-find Grafos

+10

Você recebe n nós, numerados de 0 a n-1, e uma lista edges de arestas não direcionadas. Cada par [a, b] conecta o nó a ao nó b.

Retorne true se as arestas formarem uma única árvore com todos os n nós: todo nó pode alcançar todos os outros, e não há ciclos. Caso contrário, retorne false.

Função

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: o número de nós, numerados de 0 a n-1
edgesinteger-2d-array: as arestas não direcionadas, cada uma um par [a, b]
Retornaboolean: true se as arestas conectam todos os n nós em uma árvore, false caso contrário

Restrições

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] com 0 ≤ a, b ≤ n-1 e a ≠ b
Nenhuma aresta aparece duas vezes, em nenhuma das direções.

Exemplos

Entrada: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Saída: true
Explicação: O nó 0 está conectado aos nós 1, 2 e 3, e o nó 4 está ligado ao nó 1. Quatro arestas conectam todos os cinco nós sem formar um ciclo, então isso é uma árvore.

Entrada: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Saída: false
Explicação: As arestas [1, 2], [2, 3] e [1, 3] formam o ciclo 1, 2, 3, 1. Cinco arestas em cinco nós são uma a mais do que uma árvore pode ter.

Entrada: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Saída: false
Explicação: Há 3 arestas, que é n-1, mas elas formam o ciclo 0, 1, 2, 0, e o nó 3 não tem nenhuma aresta.

Para ir além

Quando o grafo não é uma árvore, quantas arestas você precisa remover e quantas adicionar para transformá-lo em uma? É possível contar as duas em uma única passagem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma árvore é conexa e não tem ciclos. Com exatamente n-1 arestas, essas condições são equivalentes: esse grafo é conexo exatamente quando não tem ciclos. Então, verifique primeiro a quantidade de arestas e, em seguida, faça uma busca para verificar a conectividade ou deixe o union-find detectar uma aresta que conecta dois nós que já estão ligados.

Pesquise um caminho antes de cada aresta

Correta, mas não termina nos maiores testes

Intuição

Adicione as arestas uma de cada vez. Antes de adicionar [u, v], faça uma busca a partir de u pelas arestas adicionadas até então. Se v for alcançável, a nova aresta é um segundo caminho entre eles e fecha um ciclo, como [1, 3] faz no segundo exemplo. Se nenhuma aresta fechar um ciclo, o grafo é uma floresta, e uma última busca a partir do nó 0 indica se ele é uma única árvore.

cada verificação percorre todo o grafo construído até então. Em um caminho de 5001 nós cujas arestas chegam em ordem, as buscas visitam 1 + 2 + ... + 5000 nós, cerca de 12,5 milhões.

Algoritmo

Comece com uma lista de adjacência vazia para cada nó.
Para cada aresta [u, v], faça uma busca a partir de u pelas arestas adicionadas até então. Se ela alcançar v, retorne false.
Caso contrário, adicione a aresta às listas de ambas as extremidades.
Ao final, retorne se uma busca a partir do nó 0 alcança todos os n nós.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Conte as arestas e, em seguida, pesquise uma vez

Intuição

Comece com n nós separados e adicione as arestas uma a uma. Cada aresta une dois grupos, deixando um grupo a menos, ou cai dentro de um grupo e fecha um ciclo. Para chegar a um único grupo, são necessárias n-1 uniões. Portanto, menos de n-1 arestas não podem conectar o grafo, e mais arestas devem fechar um ciclo: o segundo exemplo, com 5 arestas em 5 nós, falha apenas pela contagem.

Com exatamente n-1 arestas, o grafo termina como um único grupo apenas se cada aresta tiver sido uma união, ou seja, apenas se nenhuma aresta tiver fechado um ciclo. Portanto, quando a contagem estiver correta, verifique apenas a conectividade: uma busca a partir do nó 0 deve alcançar todos os n nós. No terceiro exemplo, ela alcança apenas 0, 1 e 2. Com m = n-1, as listas e a busca têm custo O(n).

Algoritmo

Se edges.length não for n-1, retorne false.
Construa uma lista de adjacência, armazenando cada aresta em ambas as extremidades.
Empilhe o nó 0 e marque-o como visitado.
Desempilhe nós e empilhe cada vizinho ainda não visitado, marcando-o e contando-o ao empilhá-lo.
Retorne se a contagem é igual a n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Conte as arestas e a estrutura union-find

Intuição

Union-find responde à questão do ciclo para cada aresta sem fazer uma busca. Cada nó começa em seu próprio grupo. Para uma aresta [u, v], encontre a raiz de cada extremidade. Raízes diferentes: a aresta une duas partes, então mescle-as. Mesma raiz: u e v já estão conectados, e a aresta fecha um ciclo. Com n-1 arestas que todas realizam uma mesclagem, os n grupos terminam como um só: uma árvore.

Duas regras mantêm curtas as cadeias de pais. Uma mesclagem conecta a raiz do grupo menor à raiz do grupo maior, então, com 10^4 nós, nenhuma cadeia passa de 13 etapas. Durante uma busca, aponte cada nó pelo qual você passar para seu avô. Juntas, essas regras fazem com que m operações custem O(m α(n)), em que α, a função inversa de Ackermann, é no máximo 4 aqui. O espaço é O(n).

Algoritmo

Se edges.length não for n-1, retorne false.
Defina parent[x] = x e um tamanho de grupo igual a 1 para cada nó.
Para cada aresta [u, v], siga os pais a partir de u e de v até suas raízes, apontando cada nó pelo qual você passar para seu avô.
Raízes iguais: retorne false.
Raízes diferentes: vincule a raiz do grupo menor à outra e some o tamanho do grupo menor.
Se cada aresta uniu dois grupos, retorne true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    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)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

Armadilhas e casos extremos

Verificar apenas se há um ciclo. Três arestas separadas em seis nós não formam um ciclo, mas formam três componentes.
Verificar apenas a quantidade de arestas. O terceiro exemplo tem n-1 arestas, mas o ciclo 0, 1, 2 consome a aresta necessária para o nó 3.
Armazenar cada aresta apenas em uma das extremidades. [1, 0] também conecta os nós 0 e 1, e a busca a partir do nó 0 não encontra o nó 1.
Um teste de ciclo em profundidade que não ignora o nó pai. Cada aresta leva diretamente de volta ao nó de onde você veio, então “encontrou um vizinho visitado” é acionado em toda árvore.
Usar recursão em um caminho longo. Uma linha de 5001 nós chega a 5000 chamadas de profundidade, ultrapassando o limite padrão de 1000 do Python; use uma pilha explícita.

Perguntas frequentes3

Qual é a complexidade de tempo de Graph Valid Tree?

O(n + m) com uma busca em profundidade, em que m é o número de arestas, e O(n + m α(n)) com union-find. Ambos verificam primeiro a quantidade de arestas, então um grafo com uma quantidade incorreta é rejeitado antes de qualquer busca.

Por que uma árvore com n nós tem n-1 arestas?

Construa a árvore a partir de um nó e adicione os outros um de cada vez. Cada novo nó chega com exatamente uma aresta: sem nenhuma, ele ficaria desconectado; com duas, fecharia um ciclo. Portanto, n nós precisam de n-1 arestas.

Como detectar um ciclo em um grafo não direcionado?

Com union-find, uma aresta cujas duas extremidades já compartilham uma raiz fecha um ciclo. Com uma busca em profundidade, um ciclo é um vizinho visitado que não seja o nó de onde você veio, então você acompanha o pai de cada nó. Union-find não precisa nem do pai nem de uma lista de adjacência.

def validTree(n, edges):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Saída Esperada

true

Graph Valid Tree

Função

Restrições

Exemplos

Dicas

Solução

Pesquise um caminho antes de cada aresta

Conte as arestas e, em seguida, pesquise uma vez

Conte as arestas e a estrutura union-find

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos