. Redundante Verbindung

684. Redundante Verbindung

Schwierigkeitsgrad: Medium

Themen: Tiefe-First-Suche, Breite-First-Suche, Union Find, Graph

In diesem Problem ist ein Baum ein ungerichteter Graph , der angeschlossen ist und keine Zyklen hat.

Sie erhalten ein Diagramm, das als Baum mit N -Knoten von 1 bis n angeführt wurde und eine zusätzliche Kante hinzugefügt wurde. Die zugesetzte Kante hat zwei von 1 nach N ausgewählte

-Schufe und war keine bereits existierende Kante. Der Diagramm wird als Array -Kanten der Länge n dargestellt, wobei die Kanten [i] = [A i , b _i ] angeben, dass zwischen den Knoten a _i und b _i im Diagramm. return

eine Kante, die entfernt werden kann, damit der resultierende Graphen ein Baum von n Knoten

ist. Wenn es mehrere Antworten gibt, geben Sie die Antwort zurück, die in der Eingabe . auftritt Beispiel 1:

Eingabe:

Kanten = [[1,2], [1,3], [2,3]]
• Ausgabe:
[2,3]
Beispiel 2:

Eingabe:

Kanten = [[1,2], [2,3], [3,4], [1,4], [1,5]]
• Ausgabe:
[1,4]
Einschränkungen:

n == Kanten.Length

3 & lt; = n & lt; = 1000
Kanten [i] .Length == 2
1 & lt; = a
• i
& lt; b
• i _{& lt; = Kanten.length a} i
! = B
• i _{Es gibt keine wiederholten Kanten.}
Das angegebene Diagramm ist verbunden.
Lösung:

Das Problem redundante Verbindung

fordert uns auf, eine Kante in einem Diagramm zu identifizieren, das entfernt werden kann, um den Diagramm in einen gültigen Baum zu verwandeln. Ein Baum ist ein ungerichtetes Diagramm, das angeschlossen und acyclisch ist. Wir erhalten ein Diagramm, das als Baum begann, aber durch Hinzufügen einer zusätzlichen Kante modifiziert wurde. Unser Ziel ist es, diese zusätzliche Kante zu finden und zurückzugeben.

Schlüsselpunkte

Das Diagramm ist

ungerichtet

und
1. verbunden . verbunden Das resultierende Diagramm nach dem Entfernen der redundanten Kante darf keine Zyklen haben.
Die Antwort sollte die Kante zurückgeben, die
2. letztes
im Eingang im Falle mehrerer gültiger Lösungen erscheint.
3. Der Diagramm kann aufgrund der einzelnen zusätzlichen Kante höchstens einen Zyklus haben.
4. Ansatz

Der Ansatz beinhaltet die Verwendung von

Tiefe-First-Suche (DFS)

, um Zyklen zu erkennen:

Adjazenzliste Darstellung
1. :
   • Verwenden Sie eine Adjazenzliste, um die Grafik darzustellen. Diese Struktur ist geeignet, um DFS effizient durchzuführen.

2. Zykluserkennung über DFS :

   • Bevor Sie dem Diagramm eine Kante hinzufügen, überprüfen Sie DFS, um zu überprüfen, ob zwischen den beiden Scheitelpunkten der Kante bereits ein Pfad besteht. Wenn ja, würde das Hinzufügen dieser Kante einen Zyklus bilden.

3. Rückgabe der Kante :

   • Wenn ein Zyklus erkannt wird, geben Sie die aktuelle Kante als redundante Verbindung zurück.

Planen

1. die Eingangskanten analysieren.
2. Verwalten Sie eine Adjazenzliste, um die Verbindungen des Diagramms dynamisch zu verfolgen.
3. für jede Kante:
   • Verwenden Sie eine rekursive DFS -Funktion, um zu überprüfen, ob ein Pfad zwischen den beiden Scheitelpunkten besteht.
   • Wenn ein Pfad existiert, geben Sie die Kante als redundante Verbindung zurück.
   • Ansonsten fügen Sie die Kante zur Adjazenzliste hinzu.
4. Rückgeben Sie ein leeres Ergebnis, wenn keine redundante Kante gefunden wird (obwohl dies nicht gemäß den Problembeschränkungen geschieht).

implementieren wir diese Lösung in PHP: 684. Redundante Verbindung

<?php /**
 * @param Integer[][] $edges
 * @return Integer[]
 */
function findRedundantConnection($edges) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to perform DFS and check connectivity
 *
 * @param $src
 * @param $target
 * @param $visited
 * @param $adjList
 * @return bool
 */
private function isConnected($src, $target, &$visited, &$adjList) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$edges1 = [[1,2],[1,3],[2,3]];
$edges2 = [[1,2],[2,3],[3,4],[1,4],[1,5]];

print_r(findRedundantConnection($edges1)) . "\n"; // Output: [2,3]
print_r(findRedundantConnection($edges2)) . "\n"; // Output: [1,4]
?>

Erläuterung:

1. DFS -Implementierung :

   • Beginnen Sie von einem Knoten und besuchen Sie rekursiv seine Nachbarn.
   • Verwenden Sie ein besuchter Array, um die Wiederaufnahme von Knoten zu vermeiden.
   • Wenn der Zielknoten während des Traversals erreicht ist, besteht ein Weg.

2. Kantenzugabe :

   • Wenn zwischen den Scheitelpunkten der Kante kein Pfad vorhanden ist, fügen Sie die Kante der Adjazenzliste hinzu und fahren Sie mit der nächsten Kante fort.

3. redundante Kante :

   • Wenn bereits ein Pfad existiert, geben Sie die aktuelle Kante zurück, wenn er einen Zyklus bildet.

Beispielhandlung

Beispiel 1:

Eingabe : Kanten = [1, 2], [1, 3], [2, 3]]

Schritte :

1. Initialisieren Sie die Adjazenzliste als [].
2. Verarbeiten Sie die Kanten:
   • hinzufügen [1, 2] → Graph: {1: [2], 2: [1]}
   • hinzufügen [1, 3] → Graph: {1: [2, 3], 2: [1], 3: [1]}
   • prüfen [2, 3]: DFS findet einen Pfad → zurück [2, 3].

Ausgabe : [2, 3]

Beispiel 2:

Eingabe : Kanten = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

Schritte :

1. Initialisieren Sie die Adjazenzliste als [].
2. Verarbeiten Sie die Kanten:
   • hinzufügen [1, 2] → Graph: {1: [2], 2: [1]}
   • hinzufügen [2, 3] → Graph: {1: [2], 2: [1, 3], 3: [2]}
   • hinzufügen [3, 4] → Graph: {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}
   • prüfen [1, 4]: DFS findet einen Pfad → Rückgabe [1, 4].

Ausgabe : [1, 4]

Zeitkomplexität

1. DFS Traversal :

   • Für jede Kante führen wir eine DFS durch, um die Konnektivität zu überprüfen.
   • schlimmster Fall: o (v e) , wobei v die Anzahl der Eckpunkte und e ist ist die Anzahl der Kanten.

2. Gesamtkomplexität :

   • Da wir DFs für jede Kante ausführen, ist die Gesamtkomplexität o (e × (v e)) .

3. Raumkomplexität :

   • Adjazenzliste: o (v e) .
   • besuchte Array: o (v) .
   • Gesamt: o (v e) .

Ausgabe für Beispiele

Beispiel 1:

Eingabe : [[1, 2], [1, 3], [2, 3]]

Ausgabe : [2, 3]

Beispiel 2:

Eingabe : [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]

Ausgabe : [1, 4]

Das Problem kann mit einem dfs-basierten Ansatz effizient gelöst werden, um Zyklen zu erkennen. Diese Methode erstellt das Diagramm dynamisch und prüft in jedem Schritt nach redundanten Kanten. Die Lösung sorgt für die Korrektheit, indem die Problembeschränkungen einhalten und die Kante ausgibt, die einen Zyklus bildet und zuletzt im Eingang auftritt.

Kontaktlinks

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie das repository einen Stern auf GitHub geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Redundante Verbindung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!