Course Schedule
Há numCourses cursos, numerados de 0 a numCourses-1. Cada par [a, b] em prerequisites significa que você precisa concluir o curso b antes de poder começar o curso a. Retorne true se houver uma ordem em que você possa concluir todos os cursos, e false caso contrário.
Função
- numCoursesinteger
- o número de cursos
- prerequisitesinteger-2d-array
- os pares [a, b], cada um significando que o curso b vem antes do curso a
- Retornaboolean
- verdadeiro se todos os cursos puderem ser concluídos, falso caso contrário
Restrições
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Cada par
[a, b]satisfaz0 ≤ a, b < numCourses. - Nenhum par aparece duas vezes.
- Um par pode indicar o mesmo curso duas vezes,
[a, a]. Esse curso precisa de si mesmo primeiro, então nunca poderá ser cursado.
Exemplos
- Entrada
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Saída
- true
- Explicação
- O curso 0 não tem pré-requisitos, então você o faz primeiro. Isso libera o curso 1, e o curso 1 libera tanto o 2 quanto o 3, então a ordem 0, 1, 2, 3 funciona.
- Entrada
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Saída
- false
- Explicação
- O curso 0 aguarda o curso 2, o curso 2 aguarda o curso 1, e o curso 1 aguarda o curso 0. Os três ficam esperando uns pelos outros em um ciclo, então nenhum deles pode ser o primeiro que você cursa.
+20 testes ocultos ao enviar
Para ir além
Qualquer número de cursos cabe em um período, desde que os pré-requisitos de cada curso tenham sido concluídos em períodos anteriores. Qual é o menor número de períodos que abrange todos os cursos?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Desenhe cada curso como um ponto e cada par
[a, b]como uma seta debparaa. Que forma nesse desenho tornaria impossível terminar?Um ciclo de dependências. Cada curso em um ciclo espera por outro curso do mesmo ciclo, então nenhum deles pode começar primeiro. A questão é se o grafo tem um ciclo.
Conte quantos pré-requisitos ainda faltam para cada curso. Inicie uma fila com os cursos cuja contagem é 0 e, cada vez que retirar um deles, diminua a contagem de todos os cursos que dependem dele. Se menos cursos do que
numCourseschegarem à fila, há um ciclo.
Solução
Transforme os pares em um grafo direcionado com V = numCourses nós e E = prerequisites.length arestas, uma seta b → a para cada par [a, b]. Todos os cursos podem ser concluídos exatamente quando esse grafo não tem ciclos. O algoritmo de Kahn decide isso da forma como um estudante faria o planejamento: continue fazendo um curso cujos pré-requisitos já foram todos concluídos e veja se você fica sem cursos ou sem opções primeiro.
Faça todos os cursos gratuitos, rodada após rodada
Correta, mas não termina nos maiores testes
Intuição
Planeje como um estudante faria. Em cada rodada, examine todos os cursos que você ainda não fez. Se todos os pré-requisitos de um curso já foram cumpridos, faça esse curso. Repita até que uma rodada não resulte em nenhum curso feito. Se até então todos os cursos tiverem sido feitos, a resposta é verdadeira.
Por que uma rodada sem progresso significa falso: quando uma rodada não resulta em nenhum curso feito, todos os cursos restantes têm um pré-requisito que também está entre os restantes. Comece por qualquer curso restante e continue passando para um de seus pré-requisitos ainda não cumpridos. Você nunca ficará sem opções, e há apenas uma quantidade finita de cursos, então acabará voltando a um curso que já visitou. Isso é um ciclo, e os cursos nele ficam esperando uns pelos outros para sempre.
O método está correto, mas em cada rodada todos os pares e todos os cursos são examinados novamente, e uma rodada pode resultar em apenas um curso feito. Uma cadeia de 5,001 cursos, cada um exigindo o curso anterior, leva mais de 5,000 rodadas; entre 100,000 cursos, isso representa cerca de 5 × 10^8 verificações, quase todas em cursos cujo status não mudou.
Algoritmo
- Marque todos os cursos como não cursados.
- Marque um curso como bloqueado se algum par lhe der como pré-requisito um curso que não foi cursado.
- Curse todos os cursos que não foram cursados nem bloqueados.
- Se a rodada não cursou nenhum curso, pare; caso contrário, volte à etapa 2.
- Retorne true se todos os cursos tiverem sido cursados.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesBusca em profundidade com três estados
Intuição
Um ciclo é um caminho que volta ao ponto de partida. A busca em profundidade encontra um ciclo lembrando quais cursos estão no caminho que está percorrendo no momento. Dê a cada curso um de três estados: não visitado, no caminho atual e concluído.
Percorra as setas de um curso até os cursos que dependem dele. Marque um curso como "no caminho" quando entrar nele e como "concluído" quando todas as setas que saem dele tiverem sido exploradas e você voltar. Uma seta para um curso que está no caminho significa que você percorreu um círculo: retorne false. Uma seta para um curso concluído é segura, pois tudo o que pode ser alcançado a partir dele já foi verificado e não contém ciclos, então ignore-a. Cada curso é visitado uma vez e cada seta é percorrida uma vez.
Dois estados não são suficientes. No losango 0 → 1, 0 → 2, 1 → 3, 2 → 3, a busca chega ao curso 3 uma segunda vez por meio de 2, mas 3 já está concluído nesse momento, não está no caminho, e não há ciclo. Somente uma seta de volta ao caminho atual fecha um ciclo.
Escreva a busca usando sua própria pilha e, para cada curso, a posição da próxima seta ainda não explorada. A versão recursiva é mais curta, mas uma cadeia de 5,000 cursos chegaria a 5,000 chamadas de profundidade.
Algoritmo
- Para cada curso, crie a lista dos cursos que dependem dele.
- Para cada curso que ainda não foi visitado, marque-o no caminho e coloque-o em uma pilha.
- Observe o topo da pilha. Se não houver mais nenhuma seta, marque-o como concluído e remova-o da pilha; caso contrário, siga a próxima seta.
- Se a seta levar a um curso que está no caminho, retorne false. Se levar a um curso que ainda não foi visitado, marque esse curso no caminho e coloque-o na pilha.
- Quando todos os cursos estiverem concluídos, retorne true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueAlgoritmo de Kahn
Intuição
As rodadas da primeira abordagem desperdiçam tempo verificando novamente cursos que não mudaram. Um curso fica disponível em um único momento: quando seu último pré-requisito é cursado. Portanto, conte, para cada curso, quantos pré-requisitos ainda faltam, ou seja, seu grau de entrada. Quando você cursa um curso, diminua a contagem de cada curso que depende dele. Quando uma contagem chega a 0, isso significa que o curso está disponível naquele momento, então você o coloca em uma fila.
Comece a fila com todos os cursos cuja contagem é 0 desde o início e, em seguida, retire cursos da fila até que ela fique vazia. No primeiro exemplo, as contagens começam em 0, 1, 1, 1 para os cursos de 0 a 3. Ao cursar 0, a contagem do curso 1 chega a 0; ao cursar 1, as contagens dos cursos 2 e 3 chegam a 0; os quatro são cursados, então a resposta é true. Cada curso entra na fila no máximo uma vez e cada par diminui uma contagem uma vez, então o trabalho é O(V + E).
Por que um curso restante significa que há um ciclo: se a fila fica vazia enquanto o curso a não foi cursado, sua contagem está acima de 0, então um de seus pré-requisitos, b, também não foi cursado. O mesmo vale para b, e assim por diante. Um percurso do curso até um pré-requisito não cursado nunca termina, então ele revisita um curso, o que forma um ciclo. No segundo exemplo, nenhuma contagem começa em 0, a fila começa vazia e nenhum dos três cursos é cursado.
A recíproca também é válida: um curso em um ciclo depende de outro curso do mesmo ciclo, então sua contagem não pode chegar a 0 antes que esse outro seja cursado, e nenhum deles é cursado primeiro. Portanto, "todos os cursos cursados" e "nenhum ciclo" são a mesma afirmação. Como bônus, a ordem em que os cursos saíram da fila é um cronograma válido.
Algoritmo
- Para cada par [a, b], adicione a à lista de cursos que aguardam b e adicione 1 ao grau de entrada de a.
- Coloque em uma fila todos os cursos com grau de entrada 0.
- Retire um curso da fila e conte-o. Diminua o grau de entrada de cada curso que aguarda por ele e adicione à fila cada um que chegar a 0.
- Quando a fila estiver vazia, retorne se a contagem é igual a
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Armadilhas e casos extremos
A maioria dos bugs vem da direção de um par, de uma verificação de ciclo rigorosa demais ou de cursos que não aparecem em nenhum par.
- Confundir a direção.
[a, b]significa que b vem primeiro, então a seta vai de b para a e o grau de entrada de a aumenta. Criar as listas em uma direção e contar os graus de entrada na outra quebra o algoritmo. - Esquecer os cursos que não aparecem em nenhum par. Com
numCourses = 5e o único par[4, 3], os cursos 0, 1 e 2 ainda contam. Comece a fila com todos os cursos cujo grau de entrada é 0, não apenas com aqueles que você viu em um par. - Um curso que é pré-requisito de si mesmo,
[2, 2]. É um ciclo de comprimento um: seu grau de entrada nunca chega a 0 e a resposta é falsa. - Usar dois estados em vez de três na busca em profundidade. No losango 0 → 1, 0 → 2, 1 → 3, 2 → 3, o curso 3 é alcançado duas vezes, o que parece um ciclo se você só rastrear os elementos "vistos". Apenas uma seta de volta para o caminho atual fecha um ciclo.
- Recursão em cadeias longas. Uma cadeia de 5.000 cursos chega a 5.000 chamadas de profundidade, ultrapassando o limite padrão do Python de 1.000.
- Retornar true quando a fila fica vazia sem comparar o número de cursos cursados com
numCourses.
Perguntas frequentes4
Qual é a complexidade de tempo do problema de Programação de Cursos?
O(V + E), onde V é o número de cursos e E, o número de pares, usando o algoritmo de Kahn ou a busca em profundidade. A criação das listas lê cada par uma vez, cada curso entra na fila no máximo uma vez e cada par reduz uma contagem uma vez. As listas e as contagens ocupam O(V + E) de espaço.
Por que um curso que sobra no algoritmo de Kahn significa que há um ciclo?
Um curso só fica pendente se sua contagem nunca chegou a 0, então pelo menos um de seus pré-requisitos também fica pendente. Acompanhe essa espera de curso em curso: cada passo leva a outro curso pendente e, como há um número finito de cursos, o percurso precisa voltar a um que já visitou. O trecho entre as duas visitas é um ciclo.
Você deve usar BFS ou DFS para Course Schedule?
Ambos executam em O(V + E). O algoritmo de Kahn, a versão em largura primeiro, não tem profundidade de recursão com que se preocupar e fornece gratuitamente uma ordem válida dos cursos. A busca em profundidade com três estados é igualmente rápida e é a escolha natural quando você também precisa informar o ciclo, porque os cursos na pilha dela o formam.
O que é uma ordenação topológica?
Uma ordenação dos nós de um grafo direcionado na qual toda seta aponta para a frente; neste caso, uma ordenação dos cursos em que cada pré-requisito vem antes do curso que precisa dele. Ela existe exatamente quando o grafo não tem ciclos, e a ordem em que o algoritmo de Kahn percorre os cursos é uma delas. Course Schedule pergunta se existe uma ordenação topológica.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def canFinish(numCourses, prerequisites):
# Escreva o código aquiCaso 1
Caso 2
Entrada
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Esperado
true