. Trouver d'éventuels états sûrs

802. Trouvez des états sûrs éventuels

Difficulté: moyen

Sujets: Recherche de profondeur-première, recherche-première, graphique, tri topologique

Il existe un graphique dirigé de n nœuds avec chaque nœud étiqueté de 0 à n - 1. Le graphique est représenté par un graphique de tableau entier 0 indexé 2D où le graphique [i] est un tableau entier des nœuds adjacents au nœud I, ce qui signifie qu'il y a un bord du nœud I à chaque nœud dans le graphique [i].

Un nœud est un nœud terminal s'il n'y a pas de bords sortants. Un nœud est un nœud sécurisé si chaque chemin possible à partir de ce nœud mène à un nœud terminal (ou un autre nœud sûr).

return Un tableau contenant tous les nœuds de sécurité du graphique . La réponse doit être triée dans Ascendant Ordre.

Exemple 1:

• Entrée: graph = [[1,2], [2,3], [5], [0], [5], [], []]
• Sortie: [2,4,5,6]
• Explication: Le graphique donné est illustré ci-dessus. Les nœuds 5 et 6 sont des nœuds terminaux car il n'y a pas de bords sortants de l'un ou l'autre. Chaque chemin commençant par les nœuds 2, 4, 5 et 6 mène tous au nœud 5 ou 6.

Exemple 2:

• Entrée: graph = [[1,2,3,4], [1,2], [3,4], [0,4], []]
• sortie: [4]
• Explication: Seul le nœud 4 est un nœud terminal, et chaque chemin commençant au nœud 4 mène au nœud 4.

Contraintes:

• n == graph.length
• 1 & lt; = n & lt; = 10 ⁴
• 0 & lt; = graphique [i] .length & lt; = n
• 0 & lt; = graphique [i] [j] & lt; = n - 1
• Le graphique [i] est trié dans un ordre strictement croissant.
• Le graphique peut contenir des boucles d'auto-boucles.
• Le nombre de bords dans le graphique sera dans la plage [1, 4 * 10 ⁴ ].

Solution:

Nous devons identifier tous les nœuds sûrs du graphique. Cela implique de vérifier si cela à partir d'un nœud donné, chaque chemin atteint finalement un nœud terminal ou un autre nœud sûr. La solution utilise la recherche en profondeur d'abord (DFS) pour détecter les cycles et classer les nœuds comme sûrs ou dangereux.

Informations clés:

1. Nœuds terminaux : Un nœud sans bords sortants est un nœud terminal.
2. nœuds sûrs : Un nœud est sûr si, à partir de ce nœud, tous les chemins conduisent finalement à des nœuds terminaux ou à d'autres nœuds sûrs.
3. Détection du cycle : Si un nœud fait partie d'un cycle, ce n'est pas un nœud sûr car les chemins à partir de celui-ci ne mèneront pas à des nœuds terminaux.

Approche:

• Nous utilisons DFS pour explorer chaque nœud et déterminer si cela fait partie d'un cycle. Les nœuds qui font partie des cycles ou conduisent à des cycles sont marqués dangereux.
• Les nœuds qui mènent finalement à des nœuds terminaux ou à d'autres nœuds sûrs sont marqués en toute sécurité.

Nous utilisons un tableau visité avec trois états:

• 0: Le nœud n'a pas encore été visité.
• 1: Le nœud est actuellement visité (c'est-à-dire dans la pile de récursivité).
• 2: Le nœud a été entièrement traité et est sûr.

Mesures:

1. Effectuez des DF pour chaque nœud.
2. Utilisez les états visités pour marquer des nœuds sûrs / dangereux.
3. Collectez tous les nœuds en sécurité.

Implémentons cette solution dans PHP: 802. Trouvez des états sûrs éventuels

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

Explication:

1. Fonction DFS :

   • La fonction DFS effectue une recherche en profondeur d'abord sur le nœud, la marquant comme "visiter" (1) quand elle démarre et "sûr" (2) lorsque tous ses voisins sont en sécurité.
   • Si l'un de ses voisins mène à un cycle (indiqué par DFS ($ voisin) == 1), le nœud est marqué dangereux (1).
   • Si tous les voisins mènent à des nœuds terminaux ou à des nœuds sûrs, il est marqué comme sûr (2).

2. fonction principale :

   • Nous itons à travers tous les nœuds et utilisons DFS pour vérifier si chaque nœud est sûr ou non.
   • Tous les nœuds sûrs sont collectés dans le tableau $ safenodes et retournés.

Exemple de procédure pas à pas:

Exemple 1:

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

• Dans cet exemple, les nœuds 5 et 6 sont des nœuds terminaux (pas de bords sortants).
• Le nœud 4 mène au nœud 5, il est donc également sûr.
• Le nœud 2 mène au nœud 5, il est donc sûr.
• Les nœuds 1 et 0 mènent finalement à un cycle ou à des nœuds dangereux, ils ne sont donc pas en sécurité.

Sortie:

[2, 4, 5, 6]

Exemple 2:

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

• Dans cet exemple, seul le nœud 4 est un nœud terminal, et tous les chemins à partir du nœud 4 mènent au nœud 4.
• Tous les autres nœuds mènent finalement à des cycles ou des nœuds dangereux.

Sortie:

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

Complexité du temps et de l'espace:

• complexité temporelle : o (n e) , où n est le nombre de nœuds et e est le nombre de bords. Nous visitons chaque nœud une fois et traitons chaque bord une fois.
• Complexité de l'espace : o (n) pour la pile de tableau et de récursivité visité.

Cette solution détermine efficacement les nœuds sûrs à l'aide de DFS, garantissant que les contraintes de problème sont respectées.

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• LinkedIn
• github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!