Problema
Ver original (inglês)Os cursos são numerados de 0 a n−1. Cada par [curso, pré-requisito] significa que o pré-requisito deve ser feito antes do curso. Retorne uma ordem para cursar todos os cursos; quando vários cursos estiverem disponíveis, escolha sempre o de menor número primeiro para garantir uma resposta única.
Implemente course_order(n, prerequisites).
Entrada
n: O número de cursos. prerequisites: Pares [curso, pré-requisito].
Saída
Retorne a ordem dos cursos, ou uma lista vazia se houver um ciclo que torne impossível completar todos.
Restrições
1 ≤ n ≤ 100.000; 0 ≤ pares ≤ 200.000
Exemplos
Entrada:
n = 4
prerequisites = [
[1, 0],
[2, 0],
[3, 1],
[3, 2]
]
Saída esperada:
expected = [0, 1, 2, 3]Entrada:
long long n = 4;
std::vector<std::vector<long long>> prerequisites = {
{1, 0},
{2, 0},
{3, 1},
{3, 2}
};
Saída esperada:
std::vector<long long> expected = {0, 1, 2, 3};Entrada:
long n = 4;
long[][] prerequisites = new long[][] {
new long[] {1, 0},
new long[] {2, 0},
new long[] {3, 1},
new long[] {3, 2}
};
Saída esperada:
long[] expected = new long[] {0, 1, 2, 3};Explicação
0 primeiro, depois 1 e 2 (sempre o menor número primeiro), depois 3: [0, 1, 2, 3].
Entrada:
n = 2
prerequisites = [
[0, 1],
[1, 0]
]
Saída esperada:
expected = []Entrada:
long long n = 2;
std::vector<std::vector<long long>> prerequisites = {
{0, 1},
{1, 0}
};
Saída esperada:
std::vector<long long> expected = {};Entrada:
long n = 2;
long[][] prerequisites = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Saída esperada:
long[] expected = new long[] {};Explicação
Cada curso exige o outro, então não existe uma ordem possível: [].
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.