Pular para o conteúdo

Deadlock em um grafo de espera

Fácil#cycle-detection#graph-colouring#topological-sort~20 min

A missão

Problema

Um banco de dados acompanha n transações numeradas de 0 a n - 1. Cada par [a, b] em waits significa que a transação a está esperando um lock que a transação b detém. Existe um deadlock quando algum grupo de transações espera umas pelas outras em círculo. Retorne True se o grafo de espera (wait-for graph) contiver um deadlock e False caso contrário.

Exemplos

Input:  n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Por quê: 0 espera por 1, 1 por 2 e 2 por 0, então nenhuma delas consegue prosseguir
Input:  n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Por quê: duas cadeias se encontram em 3, mas se encontrar não é um círculo, e 3 não espera por ninguém
Input:  n = 2, waits = []
Output: False
Por quê: edge case: ninguém espera, então ninguém fica travado

Dicas

0 / 3

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

Restrições

  • transactions are numbered 0 to n - 1

Travou na ideia, e não no código? Ciclos em um grafo direcionado explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado