。最終的な安全な状態を見つけます-PHPチュートリアル-php.cn

。最終的な安全な状態を見つけます

DDD

リリース： 2025-01-25 06:04:14

オリジナル

939 人が閲覧しました

802。最終的な安全な状態を見つけます

難易度： medium

トピック：深度検索、幅広い最初の検索、グラフ、トポロジーソート

各ノードが0からn -1にラベル付けされたnノードの指示グラフがあります。グラフは、 0インデックス2D整数アレイグラフで表されます。ノードIに隣接するノードの。つまり、ノードIからグラフの各ノードへのエッジがある[i]。

ノードは、発信エッジがない場合は

端子ノードです。ノードは、そのノードから始まる可能性のあるすべてのパスが端子ノード（または別のセーフノード）につながる場合、セーフノードです。

グラフのすべての

セーフノードを含む配列を返します。答えは、ascending順序で並べ替える必要があります 例1：

。最終的な安全な状態を見つけます input：

graph = [[1,2]、[2,3]、[5]、[0]、[5]、[]、[]、]

output：[2,4,5,6]
説明：指定されたグラフを上に示します。ノード5と6は、どちらからも発信エッジがないため、端子ノードです。ノード2、4、5、6から始まるすべてのパスはすべてノード5または6につながります。
例2：

input：graph = [[1,2,3,4]、[1,2]、[3,4]、[0,4]、[]

output：[4]
説明：ノード4のみが端子ノードであり、ノード4から始まるすべてのパスはノード4につながります。
制約：

n == graph.length

1＆lt; = n＆lt; = 104

0＆lt; = graph [i] .length＆lt; = n
0＆lt; = graph [i] [j]＆lt; = n -1 グラフ[i]は、厳密に増加する順序でソートされます
グラフ内のエッジの数は範囲になります[1、4 * 10
]。
解決策：
グラフ内のすべての安全なノードを識別する必要があります。これには、特定のノードから起動するかどうかを確認するには、すべてのパスが最終的に端子ノードまたは別の安全ノードに到達します。ソリューションでは、深さfirst検索（DFS）を使用してサイクルを検出し、ノードを安全または安全でないものとして分類します。
主要な洞察:
1. ターミナルノード: 出力エッジのないノードはターミナルノードです。
2. 安全なノード: ノードは、そのノードから始まり、すべてのパスが最終的に終端ノードまたは他の安全なノードにつながる場合、安全です。
3. サイクル検出: ノードがサイクルの一部である場合、そのノードから始まるパスは終端ノードにつながらないため、そのノードは安全なノードではありません。
アプローチ：
- DFS を使用して各ノードを調査し、それがサイクルの一部であるかどうかを判断します。サイクルの一部であるノード、またはサイクルにつながるノードは安全でないとマークされます。
- 最終的に終端ノードまたは他の安全なノードにつながるノードは、安全であるとマークされます。
次の 3 つの状態を持つ訪問済み配列を使用します。
- 0: ノードはまだ訪問されていません。
- 1: ノードは現在アクセス中です (つまり、再帰スタック内)。
- 2: ノードは完全に処理されており、安全です。
手順:
1. 各ノードに対して DFS を実行します。
2. 訪問した状態を使用して、安全/安全でないノードをマークします。
3. 安全なノードをすべて収集します。
このソリューションを PHP で実装してみましょう: 802。最終的な安全な状態を見つける
```
<?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]
?>
```
ログイン後にコピー
ログイン後にコピー
説明：
1. DFS 関数:
  - dfs 関数はノードに対して深さ優先検索を実行し、開始時にノードを「訪問中」 (1) としてマークし、すべての隣接ノードが安全な場合は「安全」 (2) としてマークします。
  - 近隣ノードのいずれかがサイクルにつながる場合 (dfs($neighbor) == 1 で示される)、そのノードは安全でない (1) とマークされます。
  - すべての近隣ノードが終端ノードまたは安全なノードにつながっている場合、そのノードは安全 (2) としてマークされます。
2. メイン関数:
  - すべてのノードを反復処理し、DFS を使用して各ノードが安全かどうかを確認します。
  - すべての安全なノードは $safeNodes 配列に収集され、返されます。
チュートリアルの例:

例 1:
```
$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));
```
ログイン後にコピー
- この例では、ノード 5 と 6 が終端ノード (出力エッジなし) です。
- ノード 4 はノード 5 につながっているため、これも安全です。
- ノード 2 はノード 5 につながっているため、安全です。
- ノード 1 と 0 は最終的にサイクルまたは安全でないノードにつながるため、安全ではありません。
出力:
```
[2, 4, 5, 6]
```
ログイン後にコピー
例 2:
```
$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));
```
ログイン後にコピー
- この例では、ノード 4 のみが終端ノードであり、ノード 4 から始まるすべてのパスはノード 4 につながります。
- 他のすべてのノードは最終的にサイクルまたは安全でないノードにつながります。
出力:
```
<?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]
?>
```
ログイン後にコピー
ログイン後にコピー
時間と空間の複雑さ：
- 時間の複雑さ：o（n e）、ここで、n はノードの数と e はエッジの数です。各ノードに1回アクセスし、各エッジを1回処理します。
- スペースの複雑さ：o（n）訪問した配列と再帰スタックについて。
連絡先リンク

このシリーズが役立つと思った場合は、リポジトリをGitHubにスターに提供するか、お気に入りのソーシャルネットワークで投稿を共有してください。あなたのサポートは私にとって大きな意味があります！

このようなもっと役立つコンテンツが必要な場合は、お気軽にフォローしてください：

linkedIn
- github