Build adımlarını sırala
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
Bir adım, bağlı olduğu hiçbir şey beklemede kalmadığı anda çalışabilir. Hangi adımlar en başta çalışabilir?
Her adım için kaç ön koşulu hâlâ beklediğini say. Bir adımı çalıştırmak ona bağlı her adımın bu sayısını düşürür; sıfıra ulaşan bir sayı da o adımın hazır olduğu anlamına gelir.
Bir kuyruğu sayısı sıfır olan her adımla başlat. Bir adımı pop et, sıraya ekle ve ondan sonraki adımların sayılarını azalt; sıfıra ulaşanları kuyruğa ekle. Sıra n'den kısa kalırsa bir döngü geri kalanı tıkamıştır, boş bir liste döndür.
- 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
Çözüm
Bu, Kahn'ın topolojik sıralaması. Bir adımın in-degree'si hâlâ beklediği ön koşulların sayısıdır; yani in-degree'si sıfır olan adımlar tam olarak şimdi çalışabilenlerdir. Birini çalıştırmak onun giden kenarlarını kaldırır, bu da başka adımları serbest bırakabilir; bir kuyruk da onları hazır oldukça sıraya besler. Bir döngüdeki adımlar asla sıfır in-degree'ye ulaşmaz, bu yüzden sıraya hiç girmezler; kısa bir sıra da geçerli bir sıranın olmadığının sinyalidir. Her adım ve bağımlılık bir kez ele alınır; m bağımlılık için zaman O(n + m), alan O(n + m).
from collections import deque
def build_order(n, deps):
after = [[] for _ in range(n)]
waiting = [0] * n # in-degree: prerequisites still pending
for a, b in deps:
after[a].append(b)
waiting[b] += 1
ready = deque(i for i in range(n) if waiting[i] == 0)
order = []
while ready:
step = ready.popleft()
order.append(step)
for nxt in after[step]:
waiting[nxt] -= 1
if waiting[nxt] == 0: # its last prerequisite just ran
ready.append(nxt)
return order if len(order) == n else [] # short order: a loop blocked the rest
print(build_order(4, [[0, 1], [0, 2], [1, 3], [2, 3]])) # -> [0, 1, 2, 3]
print(build_order(3, [[0, 1], [1, 2], [2, 0]])) # -> []
print(build_order(3, [])) # -> [0, 1, 2]Kodda değil de fikirde mi takıldın? Topolojik sıralama bunu anlatıyor.