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 começar o curso a. Retorne true se houver alguma ordem que permita concluir todos os cursos, e false se não houver.
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]tem0 ≤ a, b < numCourses. - Nenhum par aparece duas vezes.
- Um par pode nomear o mesmo curso duas vezes,
[a, a]. Esse curso precisa de si mesmo primeiro, então nunca pode 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, que libera os cursos 2 e 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 espera pelo 2, o 2 espera pelo 1, e o 1 espera pelo 0. Os três esperam uns pelos outros em um loop, então nenhum deles pode começar primeiro.
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 necessário para cursar 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 concluir?Um ciclo de setas. 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. Comece uma fila com os cursos cuja contagem é 0 e, cada vez que você 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
Desenhe uma seta b → a para cada par [a, b]. Cada curso pode ser concluído exatamente quando esse grafo, com V = numCourses nós e E = prerequisites.length setas, não tem ciclos. O algoritmo de Kahn verifica isso da forma como um estudante planeja: continue cursando uma disciplina cujos pré-requisitos já foram concluídos e veja se todas as disciplinas são cursadas.
Pegue todos os cursos gratuitos, rodada após rodada
Correta, mas não termina nos maiores testes
Intuição
Em cada rodada, pegue todos os cursos ainda não concluídos cujos pré-requisitos já foram concluídos. Pare quando uma rodada não concluir nenhum curso e responda true se todos os cursos tiverem sido concluídos. Uma rodada não conclui nenhum curso somente quando cada curso restante depende de outro curso restante, o que forma um ciclo.
Cada rodada verifica novamente todos os pares e todos os cursos, mas pode concluir apenas um curso. Uma cadeia de 5.001 cursos entre 100,000 precisa de mais de 5.000 rodadas: cerca de 5 × 10^8 verificações.
Algoritmo
- Marque todos os cursos como não cursados.
- Marque um curso como bloqueado se algum par lhe der um pré-requisito que não foi cursado.
- Faça todos os cursos que não foram cursados nem estão bloqueados.
- Se a rodada não cursou nada, pare; caso contrário, volte à etapa 2.
- Retorne true se todos os cursos foram 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
A busca em profundidade encontra um ciclo rastreando o caminho que está percorrendo. Dê a cada curso um de três estados: não visitado, no caminho, concluído. Siga as setas de um curso até os cursos que dependem dele. Marque um curso como estando no caminho quando entrar nele e como concluído quando todas as suas setas tiverem sido exploradas.
Uma seta para um curso que está no caminho fecha um ciclo: retorne false. Uma seta para um curso concluído é segura, porque tudo que pode ser alcançado a partir dele foi verificado e não contém ciclos; portanto, um curso alcançado duas vezes não constitui, por si só, um ciclo. Cada curso é visitado uma vez e cada seta é seguida uma vez: O(V + E).
Algoritmo
- Monte, para cada curso, a lista de cursos que dependem dele.
- Para cada curso que não foi visitado, marque-o no caminho e coloque-o em uma pilha.
- Observe o topo da pilha. Se não houver nenhuma seta restante, marque-o como concluído e retire-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 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
Um curso fica disponível em um determinado momento: quando seu último pré-requisito é cursado. Portanto, mantenha o grau de entrada de cada curso, o número de pré-requisitos que ainda faltam, e inicie uma fila com todos os cursos cuja contagem é 0. Cursar um curso diminui a contagem de cada curso que depende dele, e um curso cuja contagem chega a 0 entra na fila. No primeiro exemplo, as contagens começam em 0, 1, 1, 1: cursar 0 libera 1, e cursar 1 libera 2 e 3. Cada curso entra na fila uma vez, e cada par diminui uma contagem uma vez: O(V + E).
Se a fila ficar vazia enquanto o curso a ainda não foi cursado, sua contagem é maior que 0, então algum pré-requisito de a também não foi cursado, e assim por diante. Esse percurso necessariamente revisita um curso: um ciclo. Por outro lado, cada curso em um ciclo depende de outro curso nele, então nenhum pode ser cursado primeiro. A ordem em que os cursos saem da fila é um cronograma válido.
Algoritmo
- Para cada par [a, b], adicione a à lista de cursos que aguardam por 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
- Confundir a direção.
[a, b]significa que b vem primeiro: a seta vai de b para a, e o grau de entrada de a aumenta. - Esquecer os cursos que não aparecem em nenhum par. Com
numCourses = 5e o único par[4, 3], os cursos 0, 1 e 2 também devem começar na fila. - 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 e parece um ciclo se você rastrear apenas os elementos "vistos".
- Fazer chamadas recursivas em uma cadeia de 5.000 cursos: 5.000 chamadas de profundidade, além do limite padrão de 1.000 do Python.
- Retornar true quando a fila esvaziar sem verificar se foram feitos
numCoursescursos. O segundo exemplo retornaria true.
Perguntas frequentes3
Qual é a complexidade de tempo do problema de programação de cursos?
O(V + E), em que V é o número de cursos e E é o número de pares, usando o algoritmo de Kahn ou a busca em profundidade. Cada par é lido uma vez, e cada curso é processado uma vez. As listas e as contagens ocupam O(V + E) de espaço.
Você deve usar BFS ou DFS para Course Schedule?
Ambos executam em O(V + E). O algoritmo de Kahn, a versão em largura, não tem profundidade de recursão com que se preocupar e fornece uma ordem válida dos cursos. A busca em profundidade com três estados é a escolha natural quando você também precisa indicar o ciclo, porque os cursos na pilha a formam.
O que é uma ordenação topológica?
Uma ordenação dos nós de um grafo direcionado em que todas as setas apontam para a frente; neste caso, uma ordenação 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 seleciona os cursos é uma delas. Course Schedule pergunta se existe uma ordenação desse tipo.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def canFinish(numCourses, prerequisites):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Saída Esperada
true