Saltar al contenido

Deadlock en un grafo de espera

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

La misión

Problema

Una base de datos lleva el registro de n transacciones numeradas de 0 a n - 1. Cada par [a, b] en waits significa que la transacción a está esperando un lock (bloqueo) que tiene la transacción b. Hay un deadlock (interbloqueo) cuando algún grupo de transacciones se espera entre sí en círculo. Devuelve True si el grafo de espera contiene un deadlock y False en caso contrario.

Ejemplos

Input:  n = 4, waits = [[0, 1], [1, 2], [2, 0], [3, 0]]
Output: True
Por qué: 0 espera a 1, 1 a 2 y 2 a 0, así que ninguna de ellas puede avanzar nunca
Input:  n = 4, waits = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: False
Por qué: dos cadenas se juntan en 3, pero juntarse no es un círculo, y 3 no espera a nadie
Input:  n = 2, waits = []
Output: False
Por qué: caso límite: nadie espera, así que nadie queda atascado

Pistas

0 / 3

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

Restricciones

  • transactions are numbered 0 to n - 1

¿Lo que te frena es la idea y no el código? Ciclos en un grafo dirigido lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio