Graph Valid Tree

Q: Qual è la complessità temporale di Graph Valid Tree?

O(n + m) con una ricerca in profondità, dove m è il numero di archi, e O(n + m α(n)) con union-find. Entrambi controllano prima il numero di archi, quindi un grafo con un numero errato viene rifiutato prima di qualsiasi ricerca.

MedioUnion-find Grafi

+10

Hai n nodi, numerati da 0 a n-1, e un elenco edges di archi non orientati. Ogni coppia [a, b] collega il nodo a al nodo b.

Restituisci true se gli archi formano un unico albero con tutti gli n nodi: ogni nodo può raggiungere tutti gli altri e non ci sono cicli. Altrimenti, restituisci false.

Funzione

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

ninteger: il numero di nodi, numerati da 0 a n-1
edgesinteger-2d-array: gli archi non orientati, ciascuno una coppia [a, b]
Restituisceboolean: vero se gli archi uniscono tutti gli n nodi in un unico albero, falso altrimenti

Vincoli

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] con 0 ≤ a, b ≤ n-1 e a ≠ b
Nessun arco compare due volte, in nessuna delle due direzioni.

Esempi

Input: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
Spiegazione: Il nodo 0 è collegato ai nodi 1, 2 e 3, mentre il nodo 4 dipende dal nodo 1. Quattro archi collegano tutti e cinque i nodi senza formare cicli, quindi questo è un albero.

Input: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Spiegazione: Gli archi [1, 2], [2, 3] e [1, 3] formano il ciclo 1, 2, 3, 1. Cinque archi su cinque nodi sono uno in più di quelli che può avere un albero.

Input: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Output: false
Spiegazione: Ci sono 3 archi, ovvero n-1, ma formano il ciclo 0, 1, 2, 0, e il nodo 3 non ha alcun arco.

Per approfondire

Quando il grafo non è un albero, quanti archi devi rimuovere e quanti aggiungerne per trasformarlo in un albero? Riesci a contarli entrambi in un unico passaggio?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un albero è connesso e non contiene cicli. Con esattamente n-1 archi, queste due condizioni coincidono: un grafo di questo tipo è connesso se e solo se non contiene cicli. Quindi controlla prima il numero di archi, poi cerca la connettività oppure lascia che union-find rilevi un arco che unisce due nodi già collegati.

Cerca un percorso prima di ogni bordo

Corretto, ma non termina sui test più grandi

Intuizione

Aggiungi gli archi uno alla volta. Prima di aggiungere [u, v], cerca partendo da u tra gli archi aggiunti finora. Se v è raggiungibile, il nuovo arco crea un secondo percorso tra i due nodi e chiude un ciclo, come fa [1, 3] nel secondo esempio. Se nessun arco chiude un ciclo, il grafo è una foresta e un'ultima ricerca dal nodo 0 indica se è un unico albero.

Ogni controllo esplora l'intero grafo costruito fino a quel momento. In un percorso di 5001 nodi i cui archi arrivano in ordine, le ricerche visitano 1 + 2 + ... + 5000 nodi, circa 12,5 milioni.

Algoritmo

Inizia con una lista di adiacenza vuota per ogni nodo.
Per ogni arco [u, v], cerca da u attraversando gli archi aggiunti finora. Se raggiunge v, restituisci false.
Altrimenti aggiungi l’arco alle liste di entrambi gli estremi.
Alla fine, restituisci se una ricerca dal nodo 0 raggiunge tutti gli n nodi.

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

Conta i bordi, poi cerca una volta

Intuizione

Parti da n nodi separati e aggiungi gli archi uno alla volta. Ogni arco unisce due gruppi, lasciandone uno in meno, oppure ricade all'interno di un gruppo e chiude un ciclo. Per arrivare a un solo gruppo servono n-1 unioni. Quindi, con meno di n-1 archi il grafo non può essere connesso, mentre con più archi si deve chiudere un ciclo: il secondo esempio, con 5 archi su 5 nodi, non supera già il controllo del numero.

Con esattamente n-1 archi, il grafo termina con un solo gruppo solo se ogni arco è stato un'unione, cioè solo se nessun arco ha chiuso un ciclo. Quindi, una volta verificato il numero, controlla solo la connettività: una ricerca dal nodo 0 deve raggiungere tutti i n nodi. Nel terzo esempio raggiunge solo 0, 1 e 2. Con m = n-1, le liste e la ricerca hanno costo O(n).

Algoritmo

Se edges.length non è n-1, restituisci false.
Crea una lista di adiacenza, memorizzando ogni arco sotto entrambi i suoi estremi.
Aggiungi il nodo 0 a uno stack e contrassegnalo come visitato.
Estrai i nodi dallo stack e aggiungi ogni vicino non ancora visitato, contrassegnandolo e contando ogni nodo man mano che lo aggiungi.
Restituisci se il conteggio è uguale 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

Conta gli archi e union-find

Intuizione

La struttura union-find risponde alla domanda sui cicli per ogni arco senza effettuare una ricerca. Ogni nodo inizia nel proprio gruppo. Per un arco [u, v], trova la radice di ciascuna estremità. Radici diverse: l’arco unisce due componenti, quindi fondile. Stessa radice: u e v sono già collegati e l’arco chiude un ciclo. Con n-1 archi che uniscono tutti i gruppi, gli n gruppi diventano uno solo: un albero.

Due regole mantengono corte le catene di genitori. Un’unione collega la radice del gruppo più piccolo sotto quella del gruppo più grande, quindi con 10^4 nodi nessuna catena supera 13 passaggi. Durante una ricerca, imposta il genitore di ogni nodo attraversato sul suo nonno. Insieme, queste regole fanno sì che m operazioni costino O(m α(n)), dove α, la funzione inversa di Ackermann, è al massimo 4 in questo caso. Lo spazio richiesto è O(n).

Algoritmo

Se edges.length non è n-1, restituisci false.
Imposta parent[x] = x e una dimensione del gruppo pari a 1 per ogni nodo.
Per ogni arco [u, v], segui i genitori da u e da v fino alle rispettive radici, puntando ogni nodo attraversato al suo nonno.
Radici uguali: restituisci false.
Radici diverse: collega la radice del gruppo più piccolo all'altra e aggiungi la sua dimensione.
Se ogni arco ha unito due gruppi, restituisci 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

Trappole e casi limite

Controllare solo che non ci sia un ciclo. Tre archi separati su sei nodi non formano cicli, eppure creano tre componenti.
Controllare solo il numero di archi. Il terzo esempio ha n-1 archi, ma il ciclo 0, 1, 2 occupa l’arco necessario al nodo 3.
Memorizzare ogni arco sotto una sola estremità. Anche [1, 0] collega i nodi 0 e 1, e la ricerca dal nodo 0 non trova il nodo 1.
Un controllo dei cicli in profondità che non salta il nodo padre. Ogni arco riporta direttamente al nodo da cui provieni, quindi «incontrato un vicino visitato» scatta in ogni albero.
Ricorrere su un percorso lungo. Una linea di 5001 nodi raggiunge una profondità di 5000 chiamate, superando il limite predefinito di Python, pari a 1000; usa uno stack esplicito.

Domande frequenti3

Qual è la complessità temporale di Graph Valid Tree?

O(n + m) con una ricerca in profondità, dove m è il numero di archi, e O(n + m α(n)) con union-find. Entrambi controllano prima il numero di archi, quindi un grafo con un numero errato viene rifiutato prima di qualsiasi ricerca.

Perché un albero con n nodi ha n-1 archi?

Fai crescere l’albero partendo da un nodo e aggiungi gli altri uno alla volta. Ogni nuovo nodo arriva con esattamente un arco: senza archi verrebbe separato, mentre con due chiuderebbe un ciclo. Quindi n nodi hanno bisogno di n-1 archi.

Come si rileva un ciclo in un grafo non orientato?

Con union-find, un arco i cui due estremi condividono già una radice chiude un ciclo. Con una ricerca in profondità, un ciclo è un vicino già visitato diverso dal nodo da cui sei arrivato, quindi tieni traccia del padre di ciascun nodo. Union-find non richiede né il padre né una lista di adiacenza.

def validTree(n, edges):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

true

Graph Valid Tree

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Cerca un percorso prima di ogni bordo

Conta i bordi, poi cerca una volta

Conta gli archi e union-find

Trappole e casi limite

Domande frequenti3

Problemi simili