코스일정 IV

<..> 1462. 코스 일정 IV

난이도 :

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

0에서 numcourses -1으로 표시된 총 숫자 코스가 있습니다. ]는 코스를 가져와야한다는 것을 나타냅니다.

예를 들어 쌍 [0, 1]은 코스 1을 수강하기 전에 코스 0을 가져와야 함을 나타냅니다.

전제 조건은 또한 간접 가 될 수 있습니다. 코스 A가 물론 B의 전제 조건이고 코스 B는 물론 C의 전제 조건이면 코스 A는 물론 C.

의 전제 조건입니다. queries [j] = [u

j _{, v ]가있는 배열 쿼리가 제공됩니다. j th 쿼리의 경우, 코스 u j 가 물론 v j 의 전제 조건인지 아닌지에 대한 답변을해야합니다. return 부울 배열 답변, 여기서 답변 [j]는 j th}

쿼리 . 예 1 :

입력 : numcourses = 2, 전제 조건 = [[1,0]], queries = [[0,1], [1,0]]

출력 :

[false, true] _{<:> 설명 :} 쌍 [1, 0]은 코스 0을 수강하기 전에 코스 1을 가져와야한다는 것을 나타냅니다. 코스 0은 물론 1의 전제 조건이 아니지만 그 반대는 사실입니다. ^{예제 2 :} 입력 : numcourses = 2, 전제 조건 = [], queries = [[1,0], [0,1]] _{출력 :} [false, false]

<:> 설명 :

전제 조건이없고 각 과정은 독립적입니다. ^{예 3 :}

입력 : numcourses = 3, 전제 조건 = [[1,2], [1,0], [2,0]], 쿼리 = [[1,0], [1,2]]

출력 :

[true, true] 제약 조건 :

2 & lt; = numcourses & lt; = 100
• 0 & lt; = 전제 조건 .length & lt; = (numcourses * (numcourses -1) / 2) 전제 조건 [i] .length == 2 0 & lt; = a i
, b
• i & lt; = numcourses -1
a
• i i
모든 쌍 [a

i

, b i ]은 독특합니다 전제 조건 그래프는 사이클이 없습니다 1 & lt; = queries.length & lt; = 10

4

0 & lt; = u
• i , v i
& lt; = numcourses -1
• u i i
• 힌트 :
  1. 강좌가 그래프의 노드라고 상상해 보세요. isReachable[i][j] 배열을 구축해야 합니다.
  2. 각 i 코스에서 bfs를 시작하고 방문하는 각 코스 j에 할당합니다. isReachable[i][j] = True.
  3. isReachable 배열의 쿼리에 응답합니다.

  해결책:

  그래프 표현과 Floyd-Warshall 알고리즘을 사용하여 각 코스가 다른 코스에서 접근 가능한지 여부를 계산할 수 있습니다. 이 접근 방식을 사용하면 전제 조건 관계를 효율적으로 처리하고 쿼리에 직접 답변할 수 있습니다.

  PHP에서 이 솔루션을 구현해 보겠습니다. 1462. 강좌일정IV
  

  <?php /**
   * @param Integer $numCourses
   * @param Integer[][] $prerequisites
   * @param Integer[][] $queries
   * @return Boolean[]
   */
  function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage:
  
  $numCourses = 2;
  $prerequisites = [[1,0]];
  $queries = [[0,1],[1,0]];
  
  $result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
  print_r($result); // Output: [false,true]
  
  $numCourses = 2;
  $prerequisites = [];
  $queries = [[1,0],[0,1]]
  
  $result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
  print_r($result); // Output: [false,false]
  
  $numCourses = 3;
  $prerequisites = [[1, 2], [1, 0], [2, 0]];
  $queries = [[1, 0], [1, 2]];
  
  $result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
  print_r($result); // Output: [true, true]
  ?>
  

  설명:

  1. 그래프 초기화:

     • $isReachable 2D 배열은 false로 초기화되어 처음에는 다른 코스에서 접근할 수 없음을 나타냅니다.

  2. 직접 전제 조건:

     • 전제 조건에 따라 $isReachable 배열을 채웁니다. 선수과목 [a, b]마다 반드시 a과목을 b과목보다 먼저 이수해야 합니다.

  3. 플로이드-워샬 알고리즘:

     • 이 알고리즘은 그래프의 전이적 폐쇄를 계산합니다.
     • 모든 중급 코스 k에 대해 코스 i가 코스 j에서 k까지 도달 가능한지 확인합니다. 그렇다면 $isReachable[i][j] = true로 표시합니다.

  4. 쿼리 평가:

     • 각 쿼리 [u, v]는 단순히 $isReachable[u][v] 값을 확인하여 응답됩니다.

  복잡성:

  • 시간 복잡성:
    • Floyd-Warshall 알고리즘: O(numCourses³)
    • 쿼리: O(queries.length)
    • 총계: O(numCourses³ 쿼리.길이)
  • 공간 복잡성:
    • $isReachable 배열이 사용하는 공간은 O(numCourses²)
    입니다.

  예제 연습:

  입력:

  $numCourses = 3;
  $prerequisites = [[1, 2], [1, 0], [2, 0]];
  $queries = [[1, 0], [1, 2]];
  

  실행:

  1. 그래프 초기화 후:

     $isReachable = [
         [false, false, false],
         [false, false, true],
         [false, false, false]
     ];
  

  1. 플로이드-워샬 이후:

     $isReachable = [
         [false, false, false],
         [true, false, true],
         [true, false, false]
     ];
  

  1. 질문에 답변:
     • 쿼리 [1, 0]: 참
     • 쿼리 [1, 2]: 참

  산출:

  [true, true]
  

  연락처 링크

  이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

  이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 코스일정 IV의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!