Graph Valid Tree

Q: Quelle est la complexité temporelle de Graph Valid Tree ?

O(n + m) avec une recherche en profondeur, où m est le nombre d’arêtes, et O(n + m α(n)) avec une structure union-find. Les deux vérifient d’abord le nombre d’arêtes, donc un graphe dont le nombre est incorrect est rejeté avant toute recherche.

MoyenUnion-find Graphes

+10

Tu reçois n nœuds, numérotés de 0 à n-1, ainsi qu’une liste edges d’arêtes non orientées. Chaque paire [a, b] relie le nœud a au nœud b.

Renvoie true si les arêtes forment un seul arbre avec les n nœuds : chaque nœud peut atteindre tous les autres et il n’y a aucun cycle. Renvoie false sinon.

Fonction

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

ninteger: le nombre de nœuds, numérotés de 0 à n-1
edgesinteger-2d-array: les arêtes non orientées, chacune étant une paire [a, b]
Renvoieboolean: true si les arêtes relient les n nœuds en un seul arbre, false sinon

Contraintes

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] avec 0 ≤ a, b ≤ n-1 et a ≠ b
Aucune arête n’apparaît deux fois, dans un sens ou dans l’autre.

Exemples

Entrée: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Sortie: true
Explication: Le nœud 0 est relié aux nœuds 1, 2 et 3, et le nœud 4 est rattaché au nœud 1. Quatre arêtes relient les cinq nœuds sans former de boucle : c’est donc un arbre.

Entrée: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Sortie: false
Explication: Les arêtes [1, 2], [2, 3] et [1, 3] forment la boucle 1, 2, 3, 1. Cinq arêtes sur cinq nœuds, c’est une de plus qu’un arbre ne peut en avoir.

Entrée: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Sortie: false
Explication: Il y a 3 arêtes, soit n-1, mais elles forment la boucle 0, 1, 2, 0, et le nœud 3 n’a aucune arête.

Pour aller plus loin

Lorsque le graphe n’est pas un arbre, combien d’arêtes faut-il supprimer et combien en ajouter pour en faire un arbre ? Peux-tu compter les deux en un seul parcours ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un arbre est connexe et ne contient aucun cycle. Avec exactement n-1 arêtes, ces deux propriétés équivalent à une seule condition : un tel graphe est connexe si et seulement s’il ne contient aucun cycle. Vérifie d’abord le nombre d’arêtes, puis recherche la connexité une seule fois, ou laisse union-find détecter une arête qui relie deux nœuds déjà connectés.

Cherchez un chemin avant chaque arête

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Ajoutez les arêtes une à la fois. Avant d’ajouter [u, v], effectuez une recherche à partir de u en parcourant les arêtes ajoutées jusque-là. Si v est accessible, la nouvelle arête constitue un second chemin entre ces nœuds et ferme un cycle, comme le fait [1, 3] dans le deuxième exemple. Si aucune arête ne ferme de cycle, le graphe est une forêt, et une dernière recherche à partir du nœud 0 permet de savoir s’il s’agit d’un seul arbre.

Chaque vérification explore tout le graphe construit jusque-là. Sur un chemin de 5001 nœuds dont les arêtes arrivent dans l’ordre, les recherches visitent 1 + 2 + ... + 5000 nœuds, soit environ 12,5 millions.

Algorithme

Commence avec une liste d’adjacence vide pour chaque nœud.
Pour chaque arête [u, v], effectue une recherche à partir de u en suivant les arêtes ajoutées jusque-là. Si elle atteint v, retourne false.
Sinon, ajoute l’arête aux listes des deux extrémités.
À la fin, retourne si une recherche à partir du nœud 0 atteint les n nœuds.

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

Comptez les arêtes, puis effectuez une seule recherche

Intuition

Partez de n nœuds séparés et ajoutez les arêtes une par une. Chaque arête relie soit deux groupes, ce qui réduit leur nombre d’une unité, soit tombe à l’intérieur d’un groupe et ferme un cycle. Il faut n-1 fusions pour obtenir un seul groupe. Ainsi, moins de n-1 arêtes ne peuvent pas connecter le graphe, et davantage doivent fermer un cycle : le deuxième exemple, avec 5 arêtes sur 5 nœuds, échoue au seul décompte.

Avec exactement n-1 arêtes, le graphe ne se termine avec un seul groupe que si chaque arête a été une fusion, c’est-à-dire si aucune arête n’a fermé de cycle. Une fois le décompte correct, vérifiez donc uniquement la connexité : une seule recherche à partir du nœud 0 doit atteindre les n nœuds. Dans le troisième exemple, elle n’atteint que 0, 1 et 2. Avec m = n-1, les listes et la recherche coûtent O(n).

Algorithme

Si edges.length n’est pas égal à n-1, renvoie false.
Construis une liste d’adjacence en stockant chaque arête sous ses deux extrémités.
Empile le nœud 0 et marque-le comme visité.
Dépile les nœuds et empile chaque voisin qui n’a pas encore été visité, en le marquant et en le comptant au moment de l’empiler.
Renvoie si le compte est égal à 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

Compter les arêtes et union-find

Intuition

Union-find répond à la question du cycle pour chaque arête sans recherche. Chaque nœud commence dans son propre groupe. Pour une arête [u, v], trouve la racine de chaque extrémité. Racines différentes : l’arête relie deux composantes, alors fusionne-les. Même racine : u et v sont déjà reliés et l’arête ferme un cycle. Avec n-1 arêtes qui fusionnent toutes des groupes, les n groupes n’en forment plus qu’un : un arbre.

Deux règles permettent de garder les chaînes de parents courtes. Lors d’une fusion, la racine du plus petit groupe est rattachée à celle du plus grand, de sorte qu’avec 10^4 nœuds, aucune chaîne ne dépasse 13 étapes. Pendant une recherche, fais pointer chaque nœud traversé vers son grand-parent. Ensemble, ces règles donnent un coût de O(m α(n)) pour m opérations, où α, la fonction d’Ackermann inverse, vaut au plus 4 ici. L’espace utilisé est O(n).

Algorithme

Si edges.length n’est pas égal à n-1, renvoie false.
Définis parent[x] = x et une taille de groupe de 1 pour chaque nœud.
Pour chaque arête [u, v], remonte les parents à partir de u et de v jusqu’à leurs racines, en faisant pointer chaque nœud parcouru vers son grand-parent.
Racines égales : renvoie false.
Racines différentes : rattache la racine du plus petit groupe à l’autre et additionne sa taille.
Si chaque arête a fusionné deux groupes, renvoie 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

Pièges et cas limites

Vérifier uniquement la présence d’un cycle. Trois arêtes distinctes sur six nœuds ne forment aucun cycle, mais elles constituent trois composantes.
Vérifier uniquement le nombre d’arêtes. Le troisième exemple comporte n-1 arêtes, mais le cycle 0, 1, 2 utilise l’arête dont le nœud 3 a besoin.
Stocker chaque arête sous une seule de ses extrémités. [1, 0] relie aussi les nœuds 0 et 1, et la recherche depuis le nœud 0 ne trouve pas le nœud 1.
Un test de cycle en profondeur qui n’ignore pas le parent. Chaque arête ramène directement au nœud d’où l’on vient, donc « voisin déjà visité » se déclenche pour chaque arbre.
Récursion sur un long chemin. Une ligne de 5001 nœuds atteint une profondeur de 5000 appels, au-delà de la limite par défaut de 1000 de Python ; utilisez une pile explicite.

Questions fréquentes3

Quelle est la complexité temporelle de Graph Valid Tree ?

O(n + m) avec une recherche en profondeur, où m est le nombre d’arêtes, et O(n + m α(n)) avec une structure union-find. Les deux vérifient d’abord le nombre d’arêtes, donc un graphe dont le nombre est incorrect est rejeté avant toute recherche.

Pourquoi un arbre comportant n nœuds a-t-il n-1 arêtes ?

Construisez l’arbre à partir d’un nœud et ajoutez les autres un par un. Chaque nouveau nœud arrive avec exactement une arête : sans arête, il serait isolé, et avec deux, il fermerait un cycle. Il faut donc n nœuds et n-1 arêtes.

Comment détecter un cycle dans un graphe non orienté ?

Avec union-find, une arête dont les deux extrémités partagent déjà une racine ferme un cycle. Avec un parcours en profondeur, un cycle correspond à un voisin déjà visité autre que le nœud d'où vous venez ; vous devez donc suivre le parent de chaque nœud. Union-find n'a besoin ni du parent ni d'une liste d'adjacence.

def validTree(n, edges):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true

Graph Valid Tree

Fonction

Contraintes

Exemples

Indices

Solution

Cherchez un chemin avant chaque arête

Comptez les arêtes, puis effectuez une seule recherche

Compter les arêtes et union-find

Pièges et cas limites

Questions fréquentes3

Problèmes similaires