Найди взаимоблокировку (deadlock) по графу ожидания (wait-for graph).
Граф задан как map[int][]int: ключ — id потока, значение — список id потоков,
которых он ждёт (например, держит нужные им ресурсы, а они держат ресурс, нужный
ему). Ребро A → B означает «поток A ждёт поток B».
Функция HasDeadlock(waitsFor map[int][]int) bool должна вернуть true, если в
ориентированном графе есть цикл, и false иначе. Дедлок существует тогда и
только тогда, когда поток (возможно, через цепочку) ждёт сам себя.
Учитывай и самопетлю A → A (поток ждёт сам себя) — это тоже дедлок.
HasDeadlock(map[int][]int{
1: {2},
2: {1},
})
// → true (1 ждёт 2, 2 ждёт 1 — замкнутый круг)
HasDeadlock(map[int][]int{
1: {2},
2: {3},
3: {},
})
// → false (цепочка 1 → 2 → 3, никто не ждёт по кругу)
Краевые случаи:
- пустой граф (
nil или пустая map) → false;
- одиночный узел без рёбер →
false;
- самопетля
{1: {1}} → true;
- несколько несвязанных компонент — дедлок есть, если цикл хотя бы в одной.
Теорию по взаимоблокировкам смотри в главе «Дедлоки».