İçeriğe geç

Build adımlarını sırala

Kolay#topological-sort#indegree~20 dk

Görev tanımı

Problem

Bir build'de 0'dan n - 1'e kadar numaralanmış n adım var; deps de a adımının b adımı başlamadan bitmesi gerektiği anlamına gelen [a, b] çiftlerini listeliyor. Her adımı bütün ön koşullarından sonra çalıştıran bir sıra döndür. Birkaç sıra geçerliyse herhangi biri kabul edilir. Bağımlılıklar hiçbir sıranın var olmayacağı şekilde döngüye giriyorsa boş bir liste döndür.

Örnekler

Input:  n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: [0, 1, 2, 3]
Neden: 0 önce gider, 1 ve 2 yalnız 0'a ihtiyaç duyar, 3 ikisini de bekler (2'yi 1'den önce çalıştırmak da geçerli)
Input:  n = 3, deps = [[0, 1], [1, 2], [2, 0]]
Output: []
Neden: her adım bir döngü içinde başka bir adımı bekliyor, bu yüzden hiçbiri asla başlayamaz
Input:  n = 3, deps = []
Output: [0, 1, 2]
Neden: edge case: hiç bağımlılık yokken her sıra işe yarar

İpuçları

0 / 3

Hedef zaman
O(n + m)
Hedef alan
O(n + m)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Topolojik sıralama bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case