İçeriğe geç

Wait-for graph'ta deadlock

Kolay#cycle-detection#graph-colouring#topological-sort~20 dk

Görev tanımı

Problem

Bir veritabanı 0'dan n - 1'e kadar numaralanmış n transaction'ı takip ediyor. waits'teki her [a, b] çifti, a transaction'ının b transaction'ının tuttuğu bir kilidi (lock) beklediği anlamına geliyor. Bir grup transaction bir çember halinde birbirini bekliyorsa deadlock vardır. Wait-for graph bir deadlock içeriyorsa True, değilse False döndür.

Örnekler

Input:  n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Neden: 0, 1'i; 1, 2'yi; 2 de 0'ı bekliyor, bu yüzden hiçbiri asla ilerleyemez
Input:  n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Neden: iki zincir 3'te buluşuyor ama buluşmak bir çember değil, 3 de kimseyi beklemiyor
Input:  n = 2, waits = []
Output: False
Neden: edge case: kimse beklemiyor, kimse takılı değil

İpuçları

0 / 3

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

Kısıtlar

  • transactions are numbered 0 to n - 1

Kodda değil de fikirde mi takıldın? Yönlü grafta döngüler bunu anlatıyor.

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