Redundant Connection

Q: Quelle est la complexité temporelle de Redundant Connection ?

Union-find résout le problème en un seul parcours des n arêtes : un temps O(n · α(n)), où α(n) est au plus égal à 4 en pratique, et un espace O(n). L’élimination des feuilles est également en O(n). Essayer chaque suppression avec une nouvelle recherche coûte O(n²).

MoyenUnion-find Graphes

+10

Un réseau a commencé sous forme d’arbre : n nœuds, numérotés de 1 à n, reliés par n-1 arêtes non orientées sans cycle. Puis une arête supplémentaire a été ajoutée entre deux nœuds qui n’étaient pas directement reliés, de sorte que la liste edges contient maintenant n arêtes et exactement un cycle.

Renvoie une arête que tu peux supprimer afin que les n-1 autres arêtes forment à nouveau un arbre. Si plusieurs arêtes conviennent, renvoie celle qui apparaît en dernier dans edges, sous la forme de la paire [a, b], exactement comme elle est écrite.

Fonction

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: les n arêtes non orientées, chacune étant une paire [a, b] de nœuds numérotés à partir de 1
Renvoieinteger-array: l’arête du cycle qui apparaît en dernier dans edges, écrite telle qu’elle y figure

Contraintes

3 ≤ n ≤ 5000, où n = edges.length
edges[i] = [a, b] avec 1 ≤ a, b ≤ n et a ≠ b
Aucune arête n’apparaît deux fois, dans un sens ou dans l’autre.
Les arêtes relient tous les n nœuds et forment exactement un cycle.

Exemples

Entrée: edges = [[1, 2], [1, 3], [2, 3]]
Sortie: [2, 3]
Explication: Les trois arêtes forment le triangle 1, 2, 3, donc en supprimer une laisse un arbre. [2, 3] vient en dernier dans la liste.

Entrée: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Sortie: [1, 4]
Explication: Le cycle est 1, 2, 3, 4, 1. L’arête [1, 5] n’en fait pas partie : la supprimer isolerait le nœud 5. Parmi les quatre arêtes du cycle, [1, 4] apparaît en dernier.

Pour aller plus loin

Si les arêtes étaient orientées et que le graphe d’origine était un arbre enraciné, quelle arête supprimeriez-vous lorsque l’arête supplémentaire donne deux parents à un nœud ?

Indices

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

0 sur 3 ouverts

Solution

La suppression d’une arête laisse un arbre exactement lorsque cette arête appartient à l’unique cycle du graphe ; la réponse est donc l’arête du cycle qui apparaît en dernier dans la liste. La structure union-find la trouve en un seul parcours : ajoute les arêtes dans l’ordre, et la première arête dont les extrémités sont déjà connectées est la réponse.

Essaie de supprimer chaque arête, en commençant par la dernière.

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Supprime une arête et vérifie si les n-1 autres arêtes forment un arbre. Avec n nœuds et n-1 arêtes, c’est le cas exactement lorsqu’une recherche à partir du nœud 1 atteint les n nœuds. Essaie les arêtes en partant de la fin de la liste : ainsi, la première suppression qui réussit est la plus récente. Stocke l’index de chaque arête dans les listes d’adjacence, et une recherche peut ignorer l’arête supprimée sans rien reconstruire.

Chaque essai est une recherche complète en O(n), et il peut y avoir n essais : jusqu’à 2.5 × 10^7 étapes lorsque n = 5000.

Algorithme

Construisez des listes d’adjacence qui conservent, pour chaque voisin, l’indice de l’arête qui y mène.
Pour skip, de l’indice le plus élevé jusqu’à 0, effectuez une recherche à partir du nœud 1 et ignorez l’arête d’indice skip.
Comptez les nœuds atteints par la recherche.
Si elle atteint les n nœuds, renvoyez edges[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 []

Retirez les feuilles

Intuition

Une feuille, un sommet avec une seule arête, ne peut pas appartenir à un cycle, car un cycle entre dans chacun de ses sommets et en ressort. Supprimer une feuille peut transformer son voisin en feuille : continue donc à les élaguer jusqu’à ce qu’il n’en reste aucune. Ce qui reste est exactement le cycle, puisque chaque sommet du cycle conserve ses deux arêtes de cycle. Dans le deuxième exemple, le sommet 5 est élagué, le sommet 1 conserve deux arêtes, et les sommets 1 à 4 restent.

Toute arête entre deux sommets restants est une arête du cycle, car un deuxième lien entre des sommets du cycle formerait un deuxième cycle. Parcours donc edges depuis la fin et renvoie la première arête dont les deux extrémités sont encore présentes.

Algorithme

Construisez les listes d’adjacence et comptez le degré de chaque nœud.
Empilez tous les nœuds de degré 1.
Dépilez une feuille, définissez son degré à 0 et diminuez le degré de son voisin restant ; empilez ce voisin lorsque son degré tombe à 1.
Lorsque la pile est vide, les nœuds dont le degré est supérieur à 0 forment le cycle.
Parcourez edges depuis la fin et renvoyez la première arête dont les deux extrémités restent.

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 : la première arête qui ferme une boucle

Intuition

Ajoutez les arêtes dans l’ordre de la liste et suivez les nœuds qui sont connectés. Tant que le cycle n’est pas fermé, chaque arête relie deux morceaux entre lesquels il n’existe aucun chemin. La première arête dont les extrémités sont déjà connectées ferme le cycle. Les autres arêtes du cycle ont été ajoutées avant elle : c’est donc l’arête du cycle qui apparaît en dernier. Dans le deuxième exemple, [1, 4] trouve les nœuds 1 et 4 déjà reliés, et [1, 5] n’est jamais consultée.

La structure union-find conserve un tableau, parent ; en suivant les pointeurs à partir d’un nœud, on finit par atteindre la racine de son morceau. En rattachant le morceau le plus petit au plus grand et en faisant pointer les nœuds vers leurs grands-parents pendant find, les chaînes restent courtes. Chaque opération coûte alors O(α(n)) en temps amorti, où α, la fonction inverse d’Ackermann, est au plus égale à 4 pour toute entrée réelle.

Algorithme

Faites pointer chaque nœud de 1 à n vers lui-même, parent[x] = x, et attribuez-lui une taille de 1.
Parcourez edges dans l’ordre. Pour [u, v], recherchez la racine de u et celle de v.
Si les racines correspondent, [u, v] ferme le cycle : renvoyez-le tel quel.
Sinon, la composante la plus grande absorbe la plus petite : sa racine devient le parent de la racine de la plus petite, et les tailles s’additionnent.

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 []

Pièges et cas limites

Renvoyer la dernière arête de la liste. Dans le deuxième exemple, il s’agit de [1, 5], et la supprimer coupe le nœud 5.
Parcourir la liste depuis le début après l’effeuillage. Cela renvoie la première arête du cycle, [1, 2] dans le deuxième exemple.
Trier ou inverser la paire. Si la liste contient [3, 1], renvoyer [3, 1], et non [1, 3].
Dimensionner les tableaux pour les nœuds de 0 à n-1. Les nœuds sont numérotés à partir de 1, donc le nœud n nécessite un tableau de n+1 cases.
Parcourir le cycle récursivement. Le parcours peut passer par les 5000 nœuds, soit cinq fois la limite de récursivité par défaut de Python ; utilisez donc une pile explicite et une boucle dans find.

Questions fréquentes3

Quelle est la complexité temporelle de Redundant Connection ?

Union-find résout le problème en un seul parcours des n arêtes : un temps O(n · α(n)), où α(n) est au plus égal à 4 en pratique, et un espace O(n). L’élimination des feuilles est également en O(n). Essayer chaque suppression avec une nouvelle recherche coûte O(n²).

Quelles arêtes peut-on supprimer pour obtenir un arbre ?

Exactement les arêtes du cycle. Chacune d’elles possède un autre chemin entre ses extrémités en passant par le reste du cycle, donc sa suppression préserve la connexité du graphe. Toute autre arête est le seul lien entre deux parties du graphe, et sa suppression les sépare.

Peut-on résoudre Redundant Connection avec un DFS ?

Oui. Avant d’ajouter chaque arête, effectuez une recherche à partir d’une extrémité en parcourant les arêtes déjà ajoutées ; la première arête dont l’autre extrémité est déjà accessible est la réponse. Cela coûte O(n) par arête, soit O(n²) au total, alors que la structure union-find répond à la même question en un temps quasi constant.

def findRedundantConnection(edges):
    # Écrivez le code ici

Test #1

Test #2

Argument

edges = [[1, 2], [1, 3], [2, 3]]

Résultat attendu

[2, 3]

Redundant Connection

Fonction

Contraintes

Exemples

Indices

Solution

Essaie de supprimer chaque arête, en commençant par la dernière.

Retirez les feuilles

Union-find : la première arête qui ferme une boucle

Pièges et cas limites

Questions fréquentes3

Problèmes similaires