Jadual Kursus IV

1462. Jadual Kursus IV

Kesukaran: Medium

Topik

: carian kedalaman-pertama, carian lebar-pertama, graf, jenis topologi

Terdapat sejumlah kursus numcourses yang perlu anda ambil, dilabelkan dari 0 hingga numcourses - 1. _{] menunjukkan bahawa anda} mesti _{mengambil kursus A} i pertama jika anda ingin mengambil kursus b i _{. Contohnya, pasangan [0, 1] menunjukkan bahawa anda perlu mengambil kursus 0 sebelum anda boleh mengambil kursus 1.}

Prasyarat juga boleh
• tidak langsung
. Jika kursus A adalah prasyarat tentu saja B, dan kursus B adalah prasyarat tentu saja C, maka kursus A adalah prasyarat tentu saja c.

anda juga diberi pertanyaan array di mana pertanyaan [j] = [u j , v j ]. Untuk pertanyaan, anda harus menjawab sama ada kursus u

j _{adalah prasyarat tentu saja v} j _{atau tidak.} ^kembali Jawapan array boolean, di mana jawapan [j] adalah jawapan kepada J _th pertanyaan _.

Contoh 1:

input: numCourses = 2, prasyarat = [[1,0]], queries = [[0,1], [1,0]]

output: [false, true]

• Penjelasan: Pasangan [1, 0] menunjukkan bahawa anda perlu mengambil kursus 1 sebelum anda boleh mengambil kursus 0. Kursus 0 bukanlah prasyarat tentu saja 1, tetapi sebaliknya adalah benar.
• Contoh 2:
• input:
numCourses = 2, prasyarat = [], queries = [[1,0], [0,1]]

output: [false, false]

• Penjelasan: Tidak ada prasyarat, dan setiap kursus adalah bebas.
• Contoh 3:

input:

numCourses = 3, prasyarat = [[1,2], [1,0], [2,0]], queries = [[1,0], [1,2]]

output:

[true, true]

• Kekangan:
• 2 & lt; = numcourses & lt; = 100 0 & lt; = prasquisites.length & lt; = (numcourses * (numcourses - 1) / 2)

prasyarat [i] .length == 2

0 & lt; = a i

, b

i
• & lt; = numcourses - 1
3
• semua pasangan [a
i
• , b
i
• ] adalah unik. graf prasyarat tidak mempunyai kitaran. 1 & lt; = queries.length & lt; = 10
4
• 0 & lt; = u _i , v
i
• & lt; = numcourses - 1 ₃ Petunjuk:
• 1. Bayangkan jika kursus adalah nod graf. Kita perlu membina array isreachable [i] [j].
  2. mulakan bfs dari setiap kursus saya dan berikan untuk setiap kursus j yang anda lawati isreachable [i] [j] = true.
  3. jawab pertanyaan dari array isreachable.

  Penyelesaian:

  kita boleh menggunakan perwakilan graf dan algoritma Floyd-Warshall untuk mengira sama ada setiap kursus dapat dicapai dari kursus lain. Pendekatan ini dengan cekap akan mengendalikan hubungan prasyarat dan membolehkan kita menjawab pertanyaan secara langsung. mari kita melaksanakan penyelesaian ini dalam php:

  1462. Jadual Kursus IV

  
  

  Penjelasan:

  <?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. Inisialisasi graf:
     array 2D $ isreachable diasaskan kepada palsu, mewakili bahawa tiada kursus yang dapat dicapai dari yang lain pada mulanya.
  2. Prasyarat langsung:

     Kami mengisi array $ isreachable berdasarkan prasyarat. Untuk setiap prasyarat [a, b], kursus mesti diambil sebelum kursus b.

     algoritma Floyd-Warshall:

  3. Algoritma ini mengira penutupan transitif graf.

     Untuk setiap kursus pertengahan k, kita periksa sama ada saya dapat dicapai dari kursus j melalui k. Jika ya, kami menandakan $ isreachable [i] [j] = true.
     Penilaian pertanyaan:

  4. setiap pertanyaan [u, v] dijawab dengan hanya memeriksa nilai $ isreachable [u] [v].

     Kerumitan:

  kerumitan masa:

  • algoritma Floyd-Warshall: o (numcourses
    3
    • ) pertanyaan: o (queries.length)
    • total: o (numcourses
    3
    • queries.length)
    Kerumitan ruang:
  • Ruang yang digunakan oleh array $ isreachable adalah o (numcourses
    2
    • ) .
    Contoh Walkthrough:
  Input:
  Pelaksanaan:

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

  selepas memulakan graf:
  selepas Floyd-Warshall:

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

  Menjawab Pertanyaan:

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

  pertanyaan [1, 0]: Benar
  1. pertanyaan [1, 2]: Benar
     Output:

  Pautan kenalan

  [true, true]
  

  Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberikan repositori bintang di GitHub atau berkongsi jawatan di rangkaian sosial kegemaran anda? Sokongan anda sangat bermakna bagi saya!

  Jika anda mahukan kandungan yang lebih berguna seperti ini, jangan ragu untuk mengikuti saya:

  LinkedIn

  • github

Atas ialah kandungan terperinci Jadual Kursus IV. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!