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

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
4
• ]。
• 解決策：
• グラフ内のすべての安全なノードを識別する必要があります。これには、特定のノードから起動するかどうかを確認するには、すべてのパスが最終的に端子ノードまたは別の安全ノードに到達します。ソリューションでは、深さ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）訪問した配列と再帰スタックについて。
  このソリューションは、DFSを使用して安全なノードを効率的に決定し、問題の制約が満たされていることを確認します。

  連絡先リンク

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

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

  linkedIn

  • github

以上が。最終的な安全な状態を見つけますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。