Saltar al contenido

Ordenar los pasos del build

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

La misión

Problema

Un build tiene n pasos numerados de 0 a n - 1, y deps lista pares [a, b] que significan que el paso a debe terminar antes de que empiece el paso b. Devuelve un orden que ejecute cada paso después de todos sus prerrequisitos. Si hay varios órdenes válidos, se acepta cualquiera. Si las dependencias forman un ciclo y no existe ningún orden, devuelve una lista vacía.

Ejemplos

Input:  n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: [0, 1, 2, 3]
Por qué: 0 va primero, 1 y 2 solo necesitan a 0, y 3 espera a ambos (ejecutar 2 antes que 1 también es válido)
Input:  n = 3, deps = [[0, 1], [1, 2], [2, 0]]
Output: []
Por qué: cada paso espera a otro paso en un ciclo, así que ninguno puede empezar nunca
Input:  n = 3, deps = []
Output: [0, 1, 2]
Por qué: caso límite: sin dependencias, cualquier orden funciona

Pistas

0 / 3

Tiempo objetivo
O(n + m)
Espacio objetivo
O(n + m)

Restricciones

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

¿Lo que te frena es la idea y no el código? Ordenamiento topológico lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio