Problema
Mostra originale (inglese)I corsi sono numerati da 0 a n−1. Ogni coppia [corso, prerequisito] indica che il prerequisito deve essere sostenuto prima del corso. Restituisci un ordine in cui seguire tutti i corsi; se più corsi sono disponibili, scegli sempre quello con il numero più basso per rendere la risposta univoca.
Implementa course_order(n, prerequisites).
Input
n: Il numero di corsi. prerequisites: Coppie [corso, prerequisito].
Output
Restituisci l'ordine dei corsi, oppure una lista vuota se un ciclo rende impossibile completare tutti i corsi.
Vincoli
1 ≤ n ≤ 100.000; 0 ≤ coppie ≤ 200.000
Esempi
Input:
n = 4
prerequisites = [
[1, 0],
[2, 0],
[3, 1],
[3, 2]
]
Output atteso:
expected = [0, 1, 2, 3]Input:
long long n = 4;
std::vector<std::vector<long long>> prerequisites = {
{1, 0},
{2, 0},
{3, 1},
{3, 2}
};
Output atteso:
std::vector<long long> expected = {0, 1, 2, 3};Input:
long n = 4;
long[][] prerequisites = new long[][] {
new long[] {1, 0},
new long[] {2, 0},
new long[] {3, 1},
new long[] {3, 2}
};
Output atteso:
long[] expected = new long[] {0, 1, 2, 3};Spiegazione
Prima 0, poi 1 e 2 (prima il più basso), poi 3: [0, 1, 2, 3].
Input:
n = 2
prerequisites = [
[0, 1],
[1, 0]
]
Output atteso:
expected = []Input:
long long n = 2;
std::vector<std::vector<long long>> prerequisites = {
{0, 1},
{1, 0}
};
Output atteso:
std::vector<long long> expected = {};Input:
long n = 2;
long[][] prerequisites = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Output atteso:
long[] expected = new long[] {};Spiegazione
Ogni corso richiede l'altro, quindi non esiste un ordine possibile: [].
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.