Pular para o conteúdo

Ordenar as etapas do build

Fácil#topological-sort#indegree~20 min

A missão

Problema

Um build tem n etapas numeradas de 0 a n - 1, e deps lista pares [a, b] que significam que a etapa a precisa terminar antes que a etapa b comece. Retorne uma ordem que execute cada etapa depois de todos os seus pré-requisitos. Se várias ordens forem válidas, qualquer uma delas é aceita. Se as dependências formarem um ciclo, de modo que nenhuma ordem exista, retorne uma lista vazia.

Exemplos

Input:  n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: [0, 1, 2, 3]
Por quê: 0 vai primeiro, 1 e 2 só precisam de 0, e 3 espera pelos dois (executar 2 antes de 1 também é válido)
Input:  n = 3, deps = [[0, 1], [1, 2], [2, 0]]
Output: []
Por quê: cada etapa espera por outra em um ciclo, então nenhuma consegue começar
Input:  n = 3, deps = []
Output: [0, 1, 2]
Por quê: edge case: sem dependências, qualquer ordem funciona

Dicas

0 / 3

Tempo-alvo
O(n + m)
Espaço-alvo
O(n + m)

Restrições

  • steps are numbered 0 to n - 1
  • any valid order is accepted

Travou na ideia, e não no código? Ordenação topológica explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado