Redundant Connection

Q: Wie hoch ist die Zeitkomplexität von Redundant Connection?

Union-Find löst das Problem in einem Durchlauf über die n Kanten: Laufzeit O(n · α(n)), wobei α(n) in der Praxis höchstens 4 beträgt, und Speicherbedarf O(n). Auch das Entfernen der Blätter benötigt O(n). Jede Entfernung mit einer neuen Suche auszuprobieren, kostet O(n²).

MittelUnion-Find Graphen

+10

Ein Netzwerk begann als Baum: n Knoten, nummeriert von 1 bis n, verbunden durch n-1 ungerichtete Kanten ohne Zyklus. Dann wurde eine weitere Kante zwischen zwei Knoten hinzugefügt, die nicht direkt verbunden waren, sodass die Liste edges nun n Kanten und genau einen Zyklus enthält.

Gib eine Kante zurück, die du entfernen kannst, sodass die übrigen n-1 Kanten wieder einen Baum bilden. Wenn mehrere Kanten infrage kommen, gib diejenige zurück, die zuletzt in edges erscheint, als Paar [a, b] genau so, wie es dort geschrieben steht.

Funktion

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

edgesinteger-2d-array: die n ungerichteten Kanten, jeweils ein Paar [a, b] von Knoten, die von 1 an nummeriert sind
Gibt zurückinteger-array: die Zykluskante, die zuletzt in edges erscheint, so wie sie dort steht

Einschränkungen

3 ≤ n ≤ 5000, wobei n = edges.length
edges[i] = [a, b] mit 1 ≤ a, b ≤ n und a ≠ b
Keine Kante kommt zweimal vor, auch nicht in umgekehrter Richtung.
Die Kanten verbinden alle n Knoten und enthalten genau einen Zyklus.

Beispiele

Eingabe: edges = [[1, 2], [1, 3], [2, 3]]
Ausgabe: [2, 3]
Erklärung: Die drei Kanten bilden das Dreieck 1, 2, 3, sodass das Entfernen einer beliebigen Kante einen Baum übrig lässt. [2, 3] steht in der Liste zuletzt.

Eingabe: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Ausgabe: [1, 4]
Erklärung: Der Zyklus ist 1, 2, 3, 4, 1. Die Kante [1, 5] gehört nicht dazu: Würde man sie entfernen, wäre Knoten 5 abgeschnitten. Von den vier Zykluskanten kommt [1, 4] zuletzt.

Weiterführende Frage

Wenn die Kanten gerichtet wären und der ursprüngliche Graph ein gewurzelter Baum wäre, welche Kante würdest du entfernen, wenn die zusätzliche Kante dazu führt, dass ein Knoten zwei Eltern hat?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Das Entfernen einer Kante lässt genau dann einen Baum zurück, wenn die Kante auf dem einzigen Zyklus des Graphen liegt. Die Antwort ist also die Zykluskante, die in der Liste zuletzt kommt. Union-Find findet sie in einem Durchlauf: Füge die Kanten der Reihe nach hinzu; die erste Kante, deren Endpunkte bereits verbunden sind, ist die Antwort.

Versuche, jede Kante zu entfernen, beginnend mit der letzten.

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Entferne eine Kante und prüfe, ob die übrigen n-1 Kanten einen Baum bilden. Bei n Knoten und n-1 Kanten ist das genau dann der Fall, wenn eine Suche vom Knoten 1 aus alle n Knoten erreicht. Probiere die Kanten vom Ende der Liste aus, damit die erste erfolgreiche Entfernung die letzte ist. Speichere den Index jeder Kante in den Adjazenzlisten, dann kann eine Suche die entfernte Kante überspringen, ohne etwas neu aufzubauen.

Jeder Versuch ist eine vollständige O(n)-Suche, und es kann n Versuche geben: bis zu 2.5 × 10^7 Schritte bei n = 5000.

Algorithmus

Erstelle Adjazenzlisten, die für jeden Nachbarn den Index der zu ihm führenden Kante speichern.
Durchlaufe skip vom letzten Index abwärts bis 0, starte die Suche bei Knoten 1 und ignoriere die Kante mit dem Index skip.
Zähle die Knoten, die die Suche erreicht.
Wenn sie alle n erreicht, gib edges[skip] zurück.

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

Die Blätter abziehen

Idee

Ein Blatt, ein Knoten mit einer Kante, kann nicht auf einem Zyklus liegen, da ein Zyklus jeden seiner Knoten betritt und wieder verlässt. Durch das Entfernen eines Blatts kann sein Nachbar zu einem Blatt werden; entferne also so lange Blätter, bis keines mehr übrig ist. Was bleibt, ist genau der Zyklus, da jeder Zyklusknoten seine beiden Zykluskanten behält. Im zweiten Beispiel wird Knoten 5 entfernt, Knoten 1 behält zwei Kanten, und die Knoten 1 bis 4 bleiben übrig.

Jede Kante zwischen zwei verbleibenden Knoten ist eine Zykluskante, denn eine zweite Verbindung zwischen Zyklusknoten würde einen zweiten Zyklus bilden. Durchsuche also edges vom Ende her und gib die erste Kante zurück, deren beide Enden noch vorhanden sind.

Algorithmus

Erstelle Adjazenzlisten und zähle den Grad jedes Knotens.
Lege jeden Knoten mit Grad 1 auf einen Stapel.
Nimm ein Blatt vom Stapel, setze seinen Grad auf 0 und verringere den Grad seines verbleibenden Nachbarn; lege diesen Nachbarn auf den Stapel, wenn sein Grad auf 1 sinkt.
Wenn der Stapel leer ist, bilden die Knoten mit einem Grad über 0 den Zyklus.
Durchsuche edges vom Ende her und gib die erste Kante zurück, deren beide Endpunkte noch vorhanden sind.

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: Die erste Kante, die einen Kreis schließt

Idee

Füge die Kanten in der Listenreihenfolge hinzu und verfolge, welche Knoten verbunden sind. Bis sich der Zyklus schließt, verbindet jede Kante zwei Teile, zwischen denen es keinen Pfad gibt. Die erste Kante, deren Endpunkte bereits verbunden sind, schließt den Zyklus. Die anderen Kanten des Zyklus wurden vorher hinzugefügt, daher ist es die zuletzt vorkommende Zykluskante. Im zweiten Beispiel findet [1, 4] die Knoten 1 und 4 bereits verbunden, und [1, 5] wird nie gelesen.

Die Union-Find-Datenstruktur verwendet ein Array, parent; wenn man den Zeigern eines Knotens folgt, erreicht man die Wurzel seines Teils. Wenn man den kleineren Teil unter dem größeren einhängt und bei find die Knoten auf ihre Großeltern verweisen lässt, bleiben die Ketten kurz. Jede Operation kostet dann amortisiert O(α(n)), wobei α, die inverse Ackermann-Funktion, für jede realistische Eingabe höchstens 4 beträgt.

Algorithmus

Lass jeden Knoten von 1 bis n auf sich selbst zeigen: parent[x] = x, und gib ihm die Größe 1.
Gehe edges der Reihe nach durch. Ermittle für [u, v] die Wurzel von u und die Wurzel von v.
Wenn die Wurzeln übereinstimmen, schließt [u, v] den Zyklus: Gib es wie angegeben zurück.
Andernfalls nimmt die größere Komponente die kleinere auf: Ihre Wurzel wird zum Elternknoten der kleineren Wurzel, und die Größen werden addiert.

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

Stolperfallen und Grenzfälle

Die letzte Kante der Liste zurückgeben. Im zweiten Beispiel ist das [1, 5], und wenn du sie entfernst, wird Knoten 5 abgetrennt.
Nach dem Abtragen von vorne aus suchen. Das gibt die erste Kante des Zyklus zurück, im zweiten Beispiel [1, 2].
Das Paar sortieren oder umdrehen. Wenn die Liste [3, 1] enthält, gib [3, 1] zurück, nicht [1, 3].
Arrays für Knoten von 0 bis n-1 dimensionieren. Die Knoten sind ab 1 nummeriert, daher benötigt Knoten n ein Array mit n+1 Elementen.
Rekursiv den Zyklus entlanggehen. Dabei können alle 5000 Knoten durchlaufen werden, also fünfmal so viele wie das standardmäßige Rekursionslimit von Python. Verwende daher einen expliziten Stack und eine Schleife in find.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Redundant Connection?

Union-Find löst das Problem in einem Durchlauf über die n Kanten: Laufzeit O(n · α(n)), wobei α(n) in der Praxis höchstens 4 beträgt, und Speicherbedarf O(n). Auch das Entfernen der Blätter benötigt O(n). Jede Entfernung mit einer neuen Suche auszuprobieren, kostet O(n²).

Welche Kanten können entfernt werden, sodass ein Baum übrig bleibt?

Genau die Kanten des Zyklus. Jede von ihnen hat eine zweite Route zwischen ihren Endpunkten über den restlichen Zyklus, sodass der Graph zusammenhängend bleibt, wenn man sie entfernt. Jede andere Kante ist die einzige Verbindung zwischen zwei Teilen des Graphen, und wenn man sie entfernt, werden diese getrennt.

Kann Redundant Connection mit DFS gelöst werden?

Ja. Bevor du jede Kante hinzufügst, suchst du von einem Ende aus über die bisher hinzugefügten Kanten; die erste Kante, deren anderes Ende bereits erreichbar ist, ist die Antwort. Das kostet O(n) pro Kante und insgesamt O(n²), während Union-Find dieselbe Frage in nahezu konstanter Zeit beantwortet.

def findRedundantConnection(edges):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

[2, 3]

Redundant Connection

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Versuche, jede Kante zu entfernen, beginnend mit der letzten.

Die Blätter abziehen

Union-Find: Die erste Kante, die einen Kreis schließt

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben