Cronograma de cursos I e II
Modele os pré-requisitos dos cursos como um grafo direcionado e use ordenação topológica para determinar se todos os cursos podem ser concluídos e em qual ordem.
Cronograma de cursos I e II é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Visão geral do problema
Cronograma de cursos I (LeetCode 207): dados n cursos e uma lista de pares de prerequisites [a, b] significando “b deve ser cursado antes de a”, determine se é possível concluir todos os cursos. Cronograma de cursos II (LeetCode 210): retorne a ordem real em que os cursos devem ser feitos, ou um vetor vazio se for impossível. Ambos se reduzem a uma ordenação topológica em um grafo direcionado em que os pré-requisitos são representados por arestas.
Modelagem do grafo
Construa um grafo direcionado: para cada par de pré-requisitos [a, b], adicione a aresta b → a (“b deve vir antes de a” significa que b leva a a). Calcule os graus de entrada de cada curso. Um curso com grau de entrada 0 não tem pré-requisitos e pode ser feito imediatamente. O problema é solucionável se, e somente se, não existir um ciclo nesse grafo (nenhuma dependência circular).
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))Cronograma de cursos I: solução de Kahn
Use o algoritmo de Kahn. Se o número de cursos processados for igual a n, todos poderão ser concluídos. Caso contrário, uma dependência circular impede a conclusão.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # FalseCronograma de cursos II: retornar a ordem
Faça o mesmo que em Cronograma de cursos I, mas colete a ordem dos cursos à medida que eles forem processados. Retorne a ordem se todos os cursos estiverem incluídos; caso contrário, retorne uma lista vazia.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Cronograma de cursos com DFS
Uma alternativa que usa detecção de ciclos com DFS. Os cursos têm três estados: não visitado (0), em processamento (1), concluído (2). Se alcançarmos um curso em processamento durante o DFS, existe um ciclo. Essa abordagem é funcionalmente equivalente à de Kahn, mas usa DFS recursivo.
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # FalsePor que a direção das arestas é importante
Um erro comum é inverter a direção da aresta: se o pré-requisito for [a, b], significando “b vem antes de a”, adicione a aresta b → a, não a → b. A direção da aresta deve refletir o fluxo da dependência: uma seta aponta daquilo que deve ser feito primeiro para aquilo que depende disso. Com a direção errada, a detecção de ciclos e a ordenação ficarão invertidas, produzindo resultados incorretos em problemas com várias dependências.
Cronograma de cursos III: variante gulosa
Cronograma de cursos III (LeetCode 630) é um problema diferente: os cursos têm durações e prazos, e você deseja maximizar o número de cursos feitos. Ele é resolvido de forma gulosa com uma fila de prioridade máxima: sempre escolha primeiro o curso com o prazo mais tardio; se adicionar um curso ultrapassar o prazo dele, substitua-o pelo curso mais longo feito até então (se esse curso for mais longo). Este é um problema guloso, não de ordenação topológica — isso mostra a importância de ler atentamente os enunciados.
Como lidar com nós isolados
Cursos sem pré-requisitos e sem dependentes são nós isolados — têm grau de entrada 0 e nenhuma aresta de saída. O algoritmo de Kahn os trata corretamente: eles são imediatamente adicionados à fila e processados. Certifique-se de inicializar os graus de entrada de TODOS os nós de 0 a n-1, mesmo os que não aparecem na lista de pré-requisitos, ou eles serão ignorados.
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.Tempo de conclusão de cursos em paralelo
Cursos em paralelo II: encontre o número mínimo de semestres para fazer todos os cursos quando são permitidos no máximo k cursos por semestre e os pré-requisitos devem ser respeitados. Isso exige o processamento nível a nível do algoritmo de Kahn com DP de máscara de bits para a restrição de seleção de k — um problema significativamente mais difícil que combina ordenação topológica com DP de máscara de bits.
Estratégia de comunicação em entrevistas
Ao enfrentar um problema do tipo Cronograma de cursos em uma entrevista: (1) Identifique-o imediatamente como um problema de ordenação topológica/detecção de ciclos. (2) Modele o grafo esclarecendo para qual direção as arestas apontam. (3) Escolha o algoritmo de Kahn (BFS) pela simplicidade ou o DFS por familiaridade. (4) Trate explicitamente o caso de ciclo. (5) Mencione a complexidade de tempo O(V+E). Essa abordagem estruturada demonstra habilidades sistemáticas de resolução de problemas.
Teste abrangente
Teste ambas as soluções com uma variedade de entradas para verificar a correção. A abordagem de Kahn lida bem com várias ordenações válidas — qualquer ordem topológica válida é aceitável como resposta para Cronograma de cursos II.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycleTeste rápido
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para entrevistas de programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: Cronograma de cursos I e II usam uma ordenação topológica com a aresta b → a para o pré-requisito [a, b], Cronograma de cursos I apenas verifica se o tamanho da ordem é igual a n, enquanto Cronograma de cursos II retorna a própria ordem e a detecção de ciclos baseada em DFS, com três estados, é uma alternativa válida à abordagem BFS de Kahn. A seguir, exploraremos o algoritmo de Kosaraju para componentes fortemente conexos.
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “Cronograma de cursos I e II” é grátis?
Sim — o texto completo de “Cronograma de cursos I e II” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Cronograma de cursos I e II”?
Modele os pré-requisitos dos cursos como um grafo direcionado e use ordenação topológica para determinar se todos os cursos podem ser concluídos e em qual ordem. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Cronograma de cursos I e II”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Algoritmo de Kahn: ordenação topológica por BFS
- Ordenação topológica por pós-ordem de DFS
- Cronograma de cursos I e II
- Componentes fortemente conexos com Kosaraju