Calendrier des cours IV

1462. Calendrier des cours IV

Difficulté :Moyen

Sujets : Recherche en profondeur d'abord, recherche en largeur d'abord, graphique, tri topologique

Il y a un total de numCourses cours que vous devez suivre, étiquetés de 0 à numCourses - 1. Vous recevez un tableau de prérequis où prérequis[i] = [a_i, b_i ] indique que vous devez suivre le cours a_i d'abord si tu veux suivre le cours b_i.

• Par exemple, la paire [0, 1] indique que vous devez suivre le cours 0 avant de pouvoir suivre le cours 1.

Les prérequis peuvent également être indirects. Si le cours a est un prérequis du cours b, et le cours b est un prérequis du cours c, alors le cours a est un prérequis du cours c.

Vous recevez également un tableau de requêtes où requêtes[j] = [u_j, v_j]. Pour la j^ème requête, vous devez répondre si le cours u_j est un prérequis du cours v_j ou non.

Renvoyer une réponse de tableau booléen, où réponse[j] est la réponse à la j^ième requête.

Exemple 1 :

• Entrée : numCourses = 2, prérequis = [[1,0]], requêtes = [[0,1],[1,0]]
• Sortie : [faux, vrai]
• Explication : La paire [1, 0] indique que vous devez suivre le cours 1 avant de pouvoir suivre le cours 0. Le cours 0 n'est pas un prérequis du cours 1, mais bien le contraire.

Exemple 2 :

• Entrée : numCourses = 2, prérequis = [], requêtes = [[1,0],[0,1]]
• Sortie : [faux,faux]
• Explication : Il n'y a pas de prérequis, et chaque cours est indépendant.

Exemple 3 :

• Entrée : numCourses = 3, prérequis = [[1,2],[1,0],[2,0]], requêtes = [[1,0],[1,2]]
• Sortie : [vrai, vrai]

Contraintes :

• 2
• 0
• prérequis[i].length == 2
• 0 i, b_i
• a_i != b_i
• Toutes les paires [a_i, b_i] sont uniques.
• Le graphique des prérequis n'a pas de cycles.
• 1 4
• 0 i, v_i
• u_i != v_i

Indice :

1. Imaginez si les cours sont des nœuds d'un graphique. Nous devons construire un tableau isReachable [i] [j].
2. Démarrez un BFS de chaque cours I et attribuez pour chaque cours J vous visitez Isreachable [i] [J] = True.
3. Répondez aux requêtes du tableau isReachable.

Solution:

Nous pouvons utiliser une représentation de graphique et l'algorithme de Floyd-Warshall pour calculer si chaque cours est accessible à partir d'un autre cours. Cette approche gérera efficacement les relations préalables et nous permettra de répondre directement aux requêtes.

implémentons cette solution dans PHP: 1462. Calendrier de cours 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]
?>

Explication:

1. Initialisation du graphique:

   • Le tableau 2D $ isReachable est initialisé à False, représentant qu'aucun cours n'est accessible d'un autre initialement.

2. Prérequis directs:

   • Nous remplissons le tableau $ isReachable basé sur les conditions préalables. Pour chaque condition préalable [a, b], le cours a doit être suivi avant le cours b.

3. algorithme de Floyd-Warshall:

   • Cet algorithme calcule la fermeture transitive du graphique.
   • Pour chaque cours intermédiaire K, nous vérifions si le cours I est accessible du cours j à k. Si oui, nous marquons $ isReachable [i] [j] = true.

4. Évaluation de la requête:

   • Chaque requête [u, v] est répondue en vérifiant simplement la valeur de $ isReachable [u] [v].

Complexité:

• Complexité temporelle:
  • algorithme de Floyd-Warshall: o (numCourses ³ )
  • requêtes: o (requêtes.length)
  • total: o (numCourses ³ requêtes.length)
• Complexité de l'espace:
  • L'espace utilisé par le tableau $ isreachable est o (numCourses ² ) .

Exemple de procédure pas à pas:

Saisir:

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

Exécution:

1. après avoir initialisé le graphique:

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

1. après Floyd-Warshall:

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

1. Répondre aux requêtes:
   • requête [1, 0]: vrai
   • requête [1, 2]: vrai

Sortir:

[true, true]

Contact Links

Si vous avez trouvé cette série utile, veuillez envisager de donner le dépositaire une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• LinkedIn
• github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!