Graph Valid Tree

Q: ¿Cuál es la complejidad temporal de Graph Valid Tree?

O(n + m) con una búsqueda en profundidad, donde m es el número de aristas, y O(n + m α(n)) con union-find. Ambos comprueban primero el número de aristas, así que un grafo con un número incorrecto se rechaza antes de realizar cualquier búsqueda.

MedioUnion-find Grafos

+10

Se te dan n nodos, numerados del 0 al n-1, y una lista edges de aristas no dirigidas. Cada par [a, b] conecta el nodo a con el nodo b.

Devuelve true si las aristas forman un único árbol con los n nodos: cada nodo puede llegar a todos los demás y no hay ningún ciclo. En caso contrario, devuelve false.

Función

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

ninteger: el número de nodos, numerados del 0 al n-1
edgesinteger-2d-array: las aristas no dirigidas, cada una un par [a, b]
Devuelveboolean: true si las aristas conectan los n nodos en un único árbol; false en caso contrario

Restricciones

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] con 0 ≤ a, b ≤ n-1 y a ≠ b
No aparece ninguna arista dos veces, en ninguna dirección.

Ejemplos

Entrada: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Salida: true
Explicación: El nodo 0 está conectado con los nodos 1, 2 y 3, y el nodo 4 cuelga del nodo 1. Cuatro aristas unen los cinco nodos sin formar ningún ciclo, así que esto es un árbol.

Entrada: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Salida: false
Explicación: Las aristas [1, 2], [2, 3] y [1, 3] forman el ciclo 1, 2, 3, 1. Cinco aristas en cinco nodos son una más de las que puede tener un árbol.

Entrada: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Salida: false
Explicación: Hay 3 aristas, que es n-1, pero forman el ciclo 0, 1, 2, 0, y el nodo 3 no tiene ninguna arista.

Para ir más allá

Cuando el grafo no es un árbol, ¿cuántas aristas debes eliminar y cuántas agregar para convertirlo en uno? ¿Puedes contar ambas en una sola pasada?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un árbol es conexo y no tiene ciclos. Con exactamente n-1 aristas, estas dos condiciones son equivalentes: un grafo es conexo si y solo si no tiene ciclos. Así que comprueba primero el número de aristas y después busca una vez si el grafo es conexo, o deja que union-find detecte una arista que une dos nodos que ya están conectados.

Busca un camino antes de cada arista

Correcto, pero no termina con las pruebas más grandes

Intuición

Añade las aristas una a la vez. Antes de añadir [u, v], busca desde u a través de las aristas añadidas hasta el momento. Si se puede llegar a v, la nueva arista constituye una segunda ruta entre ambos y cierra un ciclo, como ocurre con [1, 3] en el segundo ejemplo. Si ninguna arista cierra un ciclo, el grafo es un bosque, y una última búsqueda desde el nodo 0 indica si es un único árbol.

Cada comprobación busca en todo el grafo construido hasta el momento. En un camino de 5001 nodos cuyas aristas llegan en orden, las búsquedas visitan 1 + 2 + ... + 5000 nodos, unos 12,5 millones.

Algoritmo

Empieza con una lista de adyacencia vacía para cada nodo.
Para cada arista [u, v], busca desde u a través de las aristas añadidas hasta el momento. Si llega a v, devuelve false.
De lo contrario, añade la arista a las listas de ambos extremos.
Al final, devuelve si una búsqueda desde el nodo 0 llega a todos los n nodos.

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))

Cuenta las aristas, después busca una vez

Intuición

Empieza con n nodos separados y añade las aristas una por una. Cada arista une dos grupos, dejando un grupo menos, o cae dentro de un grupo y cierra un ciclo. Llegar a un solo grupo requiere n-1 uniones. Por lo tanto, con menos de n-1 aristas no se puede conectar el grafo, y con más se debe cerrar un ciclo: el segundo ejemplo, con 5 aristas en 5 nodos, falla solo por la cantidad.

Con exactamente n-1 aristas, el grafo termina como un solo grupo únicamente si cada arista fue una unión, es decir, únicamente si ninguna arista cerró un ciclo. Así que, una vez que la cantidad es correcta, comprueba solo la conectividad: una búsqueda desde el nodo 0 debe alcanzar los n nodos. En el tercer ejemplo solo alcanza 0, 1 y 2. Con m = n-1, las listas y la búsqueda cuestan O(n).

Algoritmo

Si edges.length no es n-1, devuelve false.
Construye una lista de adyacencia, almacenando cada arista en ambos extremos.
Apila el nodo 0 y márcalo como visitado.
Desapila nodos y apila cada vecino que aún no haya sido visitado, marcándolo y contabilizándolo al apilarlo.
Devuelve si el recuento es 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

Cuenta las aristas y la estructura union-find

Intuición

Union-find responde a la pregunta sobre ciclos para cada arista sin buscar. Cada nodo comienza en su propio grupo. Para una arista [u, v], encuentra la raíz de cada extremo. Si las raíces son distintas, la arista une dos componentes, así que fusiónalas. Si tienen la misma raíz, u y v ya están conectados y la arista cierra un ciclo. Con n-1 aristas que se fusionan todas, los n grupos terminan formando uno solo: un árbol.

Dos reglas mantienen cortas las cadenas de padres. Una fusión coloca la raíz del grupo más pequeño bajo la raíz del grupo más grande, así que con 10^4 nodos ninguna cadena supera 13 pasos. Durante una búsqueda, apunta cada nodo por el que pases a su abuelo. Juntas, estas reglas hacen que m operaciones cuesten O(m α(n)), donde α, la función inversa de Ackermann, es como máximo 4 aquí. El espacio es O(n).

Algoritmo

Si edges.length no es n-1, devuelve false.
Establece parent[x] = x y un tamaño de grupo de 1 para cada nodo.
Para cada arista [u, v], sigue los padres desde u y desde v hasta sus raíces, apuntando cada nodo por el que pases a su abuelo.
Raíces iguales: devuelve false.
Raíces diferentes: une la raíz del grupo más pequeño al otro y suma su tamaño.
Si cada arista fusionó dos grupos, devuelve 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

Errores comunes y casos límite

Comprobar solo si hay un ciclo. Tres aristas separadas en seis nodos no tienen ningún ciclo, pero forman tres componentes.
Comprobar solo la cantidad de aristas. El tercer ejemplo tiene n-1 aristas, pero el ciclo 0, 1, 2 consume la arista que necesita el nodo 3.
Almacenar cada arista solo bajo uno de sus extremos. [1, 0] también conecta los nodos 0 y 1, y la búsqueda desde el nodo 0 no encuentra el nodo 1.
Una prueba de ciclos en profundidad que no omite el nodo padre. Cada arista lleva directamente de vuelta al nodo del que vienes, así que «encontró un vecino visitado» se activa en todos los árboles.
Recurrir en un camino largo. Una línea de 5001 nodos alcanza una profundidad de 5000 llamadas, superando el límite predeterminado de Python de 1000; usa una pila explícita.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Graph Valid Tree?

O(n + m) con una búsqueda en profundidad, donde m es el número de aristas, y O(n + m α(n)) con union-find. Ambos comprueban primero el número de aristas, así que un grafo con un número incorrecto se rechaza antes de realizar cualquier búsqueda.

¿Por qué un árbol con n nodos tiene n-1 aristas?

Haz crecer el árbol desde un nodo y añade los demás uno a uno. Cada nodo nuevo llega con exactamente una arista: sin ninguna, quedaría desconectado, y con dos, cerraría un ciclo. Así que n nodos necesitan n-1 aristas.

¿Cómo detectas un ciclo en un grafo no dirigido?

Con union-find, una arista cuyos dos extremos ya comparten una raíz cierra un ciclo. Con una búsqueda en profundidad, un ciclo es un vecino visitado que no es el nodo desde el que llegaste, así que llevas un registro del padre de cada nodo. Union-find no necesita ni el padre ni una lista de adyacencia.

def validTree(n, edges):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

true

Graph Valid Tree

Función

Restricciones

Ejemplos

Pistas

Solución

Busca un camino antes de cada arista

Cuenta las aristas, después busca una vez

Cuenta las aristas y la estructura union-find

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares