Найти потенциальный дедлок по порядку захвата мьютексов
Условие
Профилировщик записал, в каком порядке потоки захватывают и отпускают мьютексы. Если какой-то поток захватывает мьютекс B, удерживая A, говорим, что в программе есть порядок A → B. Если порядки образуют цикл (например, где-то A → B, а где-то B → A), при неудачном расписании возможен дедлок. Повторный захват уже удерживаемого мьютекса тем же потоком (A → A) тоже считается дедлоком.
Если цикла нет, выведите SAFE и единый допустимый порядок захвата всех упомянутых мьютексов: лексикографически наименьший (по кодам символов имён) порядок, согласованный со всеми найденными A → B. Иначе выведите DEADLOCK.
Ввод: число потоков t (1 ≤ t ≤ 100). Далее для каждого потока строка: число операций и сами операции +name (захват) или -name (освобождение). Захваты правильно вложены, в конце поток всё отпускает. Всего операций не больше 4000, имён не больше 200.
Вывод: SAFE и порядок через пробел, или DEADLOCK.
Пример 1
Ввод:
2
4 +a +b -b -a
4 +b +a -a -b
Вывод:
DEADLOCK
Пример 2
Ввод:
2
4 +a +b -b -a
4 +a +c -c -a
Вывод:
SAFE a b c
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.