. Finden Sie eventuelle sichere Zustände

802. Finden Sie eventuelle sichere Zustände

Schwierigkeit:Mittel

Themen: Tiefensuche, Breitensuche, Diagramm, Topologische Sortierung

Es gibt einen gerichteten Graphen mit n Knoten, wobei jeder Knoten mit 0 bis n - 1 beschriftet ist. Der Graph wird durch einen 0-indizierten 2D-Integer-Array-Graph dargestellt, wobei graph[i] ein Integer-Array ist von Knoten neben Knoten i, was bedeutet, dass es eine Kante vom Knoten i zu jedem Knoten in Graph[i] gibt.

Ein Knoten ist ein Endknoten, wenn es keine ausgehenden Kanten gibt. Ein Knoten ist ein sicherer Knoten, wenn jeder mögliche Pfad, der von diesem Knoten ausgeht, zu einem Endknoten (oder einem anderen sicheren Knoten) führt.

Gibt ein Array zurück, das alle sicheren Knoten des Diagramms enthält. Die Antwort sollte in aufsteigender Reihenfolge sortiert werden.

Beispiel 1:

• Eingabe: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
• Ausgabe: [2,4,5,6]
• Erklärung: Die angegebene Grafik ist oben dargestellt. Die Knoten 5 und 6 sind Endknoten, da von keinem von ihnen ausgehende Kanten vorhanden sind. Jeder Pfad, der an den Knoten 2, 4, 5 und 6 beginnt, führt entweder zu Knoten 5 oder 6.

Beispiel 2:

• Eingabe: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
• Ausgabe: [4]
• Erklärung:Nur ​​Knoten 4 ist ein Endknoten und jeder Pfad, der bei Knoten 4 beginnt, führt zu Knoten 4.

Einschränkungen:

• n == graph.length
• 1 4
• 0
• 0
• graph[i] ist in streng aufsteigender Reihenfolge sortiert.
• Das Diagramm kann Selbstschleifen enthalten.
• Die Anzahl der Kanten im Diagramm liegt im Bereich [1, 4 * 10⁴].

Lösung:

Wir müssen alle sicheren Knoten im Diagramm identifizieren. Dabei wird überprüft, ob jeder Pfad ausgehend von einem bestimmten Knoten schließlich einen Endknoten oder einen anderen sicheren Knoten erreicht. Die Lösung nutzt Depth-First Search (DFS), um Zyklen zu erkennen und Knoten als sicher oder unsicher zu klassifizieren.

Wichtige Erkenntnisse:

1. Endknoten: Ein Knoten ohne ausgehende Kanten ist ein Endknoten.
2. Sichere Knoten: Ein Knoten ist sicher, wenn alle Pfade von diesem Knoten aus schließlich zu Endknoten oder anderen sicheren Knoten führen.
3. Zykluserkennung: Wenn ein Knoten Teil eines Zyklus ist, ist er kein sicherer Knoten, da von ihm ausgehende Pfade nicht zu Endknoten führen.

Ansatz:

• Wir verwenden DFS, um jeden Knoten zu untersuchen und festzustellen, ob er Teil eines Zyklus ist. Knoten, die Teil von Zyklen sind oder zu Zyklen führen, werden als unsicher markiert.
• Knoten, die schließlich zu Endknoten oder anderen sicheren Knoten führen, werden als sicher markiert.

Wir verwenden ein besuchtes Array mit drei Zuständen:

• 0: Der Knoten wurde noch nicht besucht.
• 1: Der Knoten wird gerade besucht (d. h. im Rekursionsstapel).
• 2: Der Knoten wurde vollständig verarbeitet und ist sicher.

Schritte:

1. Führen Sie DFS für jeden Knoten durch.
2. Verwenden Sie die besuchten Zustände, um sichere/unsichere Knoten zu markieren.
3. Sammeln Sie alle sicheren Knoten.

Lassen Sie uns diese Lösung in PHP implementieren: 802. Finden Sie mögliche sichere Zustände

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

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

Erläuterung:

1. DFS-Funktion:

   • Die DFS-Funktion führt eine Tiefensuche auf dem Knoten durch und markiert ihn als „besuchend“ (1), wenn er startet, und als „sicher“ (2), wenn alle seine Nachbarn sicher sind.
   • Wenn einer seiner Nachbarn zu einem Zyklus führt (angezeigt durch dfs($neighbor) == 1), wird der Knoten als unsicher (1) markiert.
   • Wenn alle Nachbarn zu Endknoten oder sicheren Knoten führen, wird es als sicher (2) markiert.

2. Hauptfunktion:

   • Wir durchlaufen alle Knoten und verwenden DFS, um zu prüfen, ob jeder Knoten sicher ist oder nicht.
   • Alle sicheren Knoten werden im Array $safeNodes gesammelt und zurückgegeben.

Beispielhafte Vorgehensweise:

Beispiel 1:

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));

• In diesem Beispiel sind die Knoten 5 und 6 Endknoten (keine ausgehenden Kanten).
• Knoten 4 führt zu Knoten 5, daher ist er auch sicher.
• Knoten 2 führt zu Knoten 5, also ist er sicher.
• Knoten 1 und 0 führen schließlich zu einem Zyklus oder unsicheren Knoten, sodass sie nicht sicher sind.

Ausgabe:

[2, 4, 5, 6]

Beispiel 2:

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));

• In diesem Beispiel ist nur Knoten 4 ein Endknoten und alle Pfade, die von Knoten 4 beginnen, führen zu Knoten 4.
• Alle anderen Knoten führen schließlich zu Zyklen oder unsicheren Knoten.

Ausgabe:

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

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

Zeit und Raumkomplexität:

• Zeitkomplexität : o (n e) , wobei n die Anzahl der Knoten und e
ist die Anzahl der Kanten. Wir besuchen jeden Knoten einmal und verarbeiten jede Kante einmal.
• Raumkomplexität : o (n)
Für das besuchte Array- und Rekursionsstapel.

Diese Lösung bestimmt effizient die sicheren Knoten mit DFS und stellt sicher, dass die Problembeschränkungen erfüllt sind.

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. Finden Sie eventuelle sichere Zustände. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!