. 최종 안전 상태를 찾으십시오

802. 최종 안전 상태를 찾으십시오 난이도 :

중간 주제 : 깊이 우선 검색, 폭이 넓은 첫 번째 검색, 그래프, 토폴로지 정렬

각 노드가 0 내지 n -1로 표시된 N 노드의 지시 된 그래프가 있습니다. 그래프는 그래프 [i]가 정수 배열 인 A 0 -indexed 2d Integer 배열 그래프로 표시됩니다. 노드 i에 인접한 노드의 경우, 그래프 [i]. 노드는 나가는 가장자리가없는 경우 터미널 노드 입니다. 노드는 안전 노드 입니다. 해당 노드에서 시작하는 모든 경로가 터미널 노드

(또는 다른 안전 노드)로 이어지는 경우. return return 그래프 의 모든 안전 노드

를 포함하는 배열. 대답은

오름차순 순서로 정렬되어야합니다 예 1 :

입력 : 그래프 = [[1,2], [2,3], [5], [0], [5], [], []] 출력 : [2,4,5,6] <:> 설명 : 주어진 그래프는 위에 표시되어 있습니다. 노드 5와 6은 그 중 하나의 나가는 가장자리가 없기 때문에 터미널 노드입니다. 노드 2, 4, 5 및 6에서 시작하는 모든 경로는 모두 노드 5 또는 6으로 이어집니다.

예제 2 : 입력 : 그래프 = [[1,2,3,4], [1,2], [3,4], [0,4], []] 출력 :

[4]

<:> 설명 : 노드 4만이 터미널 노드이며 노드 4에서 시작하는 모든 경로는 노드 4로 이어집니다. 제약 조건 :

n == Graph.length 1 & lt; = n & lt; = 10 4

0 & lt; = 그래프 [i] .length & lt; = n
• 0 & lt; = 그래프 [i] [j] & lt; = n -1 그래프 [i]는 엄격하게 증가하는 순서로 정렬됩니다 그래프에는 셀프 루프가 포함될 수 있습니다 그래프의 가장자리 수는 범위 [1, 4 * 10
4
• ]. 솔루션 : 우리는 그래프에서 모든 안전 노드를 식별해야합니다. 여기에는 주어진 노드에서 시작하는지 확인하는 것이 포함되며, 모든 경로는 결국 터미널 노드 또는 다른 안전 노드에 도달합니다. 이 솔루션은 깊이 우선 검색 (DFS)을 사용하여 사이클을 감지하고 노드를 안전하거나 안전하지 않은 것으로 분류합니다.

  주요 통찰력:

  1. 터미널 노드: 나가는 에지가 없는 노드는 터미널 노드입니다.
  2. 안전 노드: 해당 노드에서 시작하여 모든 경로가 결국 터미널 노드나 다른 안전 노드로 연결되면 해당 노드는 안전합니다.
  3. 주기 감지: 노드가 주기의 일부인 경우 해당 노드에서 시작하는 경로가 터미널 노드로 연결되지 않으므로 안전한 노드가 아닙니다.

  접근하다:

  • 우리는 DFS를 사용하여 각 노드를 탐색하고 그것이 주기의 일부인지 확인합니다. 순환의 일부이거나 순환으로 이어지는 노드는 안전하지 않은 것으로 표시됩니다.
  • 결국 터미널 노드나 다른 안전한 노드로 연결되는 노드는 안전하다고 표시됩니다.

  세 가지 상태의 방문 배열을 사용합니다.

  • 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 는 가장자리의 수입니다. 우리는 각 노드를 한 번 방문하고 각 모서리를 한 번 처리합니다. 공간 복잡성 :
  o (n)
  • 방문 된 배열 및 재귀 스택의 경우. 이 솔루션은 DFS를 사용하여 안전한 노드를 효율적으로 결정하여 문제 제약이 충족되도록합니다. 연락처 링크 이 시리즈가 도움이된다면 리포지토리 Github에 별을 주거나 좋아하는 소셜 네트워크에서 게시물을 공유하는 것이 무엇입니까? 당신의 지원은 나에게 큰 의미가 있습니다! 이와 같은 유용한 콘텐츠를 원한다면 언제든지 나를 따르십시오 :
  LinkedIn
  github

위 내용은 . 최종 안전 상태를 찾으십시오의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!