Детект дедлока через wait-for графDeadlock detection via a wait-for graph

Дано n активных транзакций (пронумерованы 0..n-1) и список пар `waits[i] = [a, b]`, означающий "транзакция a ждёт освобождения ресурса, удерживаемого транзакцией b". Нужно определить, есть ли в системе дедлок (взаимная блокировка), и если да — вернуть номер любой транзакции, входящей в цикл ожидания, которую можно откатить, чтобы разрешить затор. Если дедлока нет — вернуть -1.Given n active transactions (numbered 0..n-1) and a list of pairs `waits[i] = [a, b]`, meaning "transaction a is waiting for a resource held by transaction b." Determine whether the system has a deadlock (mutual blocking), and if so, return the number of any transaction in the wait cycle that can be rolled back to break it. If there's no deadlock, return -1.

// Example
n = 4, waits = [[0,1],[1,2],[2,0],[3,1]]
// output: 0, 1 илиor 2  (любая транзакция из цикла 0→1→2→0)(any transaction from the cycle 0→1→2→0)

Первый шаг — тот же перевод, что в 3.1.2: "a ждёт b" — это ориентированное ребро a→b. Список `waits` — это список рёбер ориентированного графа на n вершинах (транзакциях). Дедлок в реальной системе означает буквально: транзакция 0 не может продолжить, пока не освободится ресурс у 1, но 1 сама ждёт 2, а 2 ждёт освобождения у 0 — замкнутый круг, где никто не может быть первым. Это ровно определение цикла в графе, введённое в 3.1.1: путь, начинающийся и заканчивающийся в одной вершине.The first step is the same translation as in 3.1.2: "a waits for b" is a directed edge a→b. The `waits` list is the edge list of a directed graph on n vertices (transactions). A real deadlock literally means: transaction 0 can't proceed until 1 releases its resource, but 1 is itself waiting on 2, and 2 is waiting on 0 — a closed loop where nobody can go first. That is exactly 3.1.1's definition of a cycle: a path that starts and ends at the same vertex.

Второй шаг — вспомнить конкретный механизм из 3.1.2: DFS обнаруживает цикл в ориентированном графе через back edge — ребро, ведущее в вершину, которая уже находится в текущем стеке рекурсии (то есть мы вернулись туда, откуда уже начинали путь). Для этого достаточно двух массивов состояний: `visited` (вершина обработана когда-либо, неважно когда) и `inStack` (вершина находится в ТЕКУЩЕЙ цепочке рекурсии прямо сейчас). Если DFS из вершины u доходит до соседа v, для которого `inStack[v] == true`, — v и есть та точка, где цикл замкнулся, а значит она входит в дедлок.The second step is recalling the specific mechanism from 3.1.2: DFS detects a cycle in a directed graph via a back edge — an edge leading to a vertex that's already on the current recursion stack (meaning we've looped back to somewhere the path already visited). Two state arrays suffice: `visited` (the vertex has been processed at some point, doesn't matter when) and `inStack` (the vertex is on the CURRENT recursion chain right now). If DFS from vertex u reaches a neighbor v for which `inStack[v] == true`, v is exactly where the cycle closed, meaning it's part of the deadlock.

Важная деталь, которую 3.1.2 подчёркивал в разделе "Грабли": путать `visited` (вершина обработана вообще) с `inStack` (вершина в цепочке прямо сейчас) — частая ошибка. Транзакция 3 будет помечена `visited`, когда DFS до неё дойдёт, но она никогда не окажется в цикле — использование только `visited` для проверки цикла дало бы ложные срабатывания на графах со сходящимися, но не зацикленными путями.A detail 3.1.2 stressed in its "Gotchas" section: confusing `visited` (the vertex has been processed at all) with `inStack` (the vertex is on the chain right now) is a common mistake. Transaction 3 will be marked `visited` once DFS reaches it, but it will never end up in a cycle — using only `visited` to check for a cycle would produce false positives on graphs with converging but non-looping paths.

class Solution {
    std::vector<int> cyclePath;

    bool dfs(int u, const std::vector<std::vector<int>>& adj,
             std::vector<bool>& visited, std::vector<bool>& inStack) {
        visited[u] = true;
        inStack[u] = true;
        for (int v : adj[u]) {
            if (inStack[v]) {                 // back edge — нашли цикл// back edge — found a cycle
                cyclePath = {u, v};
                return true;
            }
            if (!visited[v] && dfs(v, adj, visited, inStack)) return true;
        }
        inStack[u] = false;                     // выходим из цепочки — освобождаем// leaving the chain — release it
        return false;
    }

public:
    int findDeadlockVictim(int n, std::vector<std::vector<int>>& waits) {
        std::vector<std::vector<int>> adj(n);
        for (auto& e : waits) adj[e[0]].push_back(e[1]);

        std::vector<bool> visited(n, false), inStack(n, false);
        for (int t = 0; t < n; ++t) {
            if (!visited[t] && dfs(t, adj, visited, inStack))
                return cyclePath[1];          // любая транзакция из найденного цикла// any transaction from the found cycle
        }
        return -1;                            // дедлока нет// no deadlock
    }
};

Сложность O(V + E), как и в базовом DFS из 3.1.2: каждая вершина и каждое ребро обрабатываются не более одного раза благодаря `visited`. Внешний цикл по всем t от 0 до n-1 — это ровно та защита "от несвязного графа" из раздела "Грабли" в 3.1.2: транзакции без входящих рёбер от уже проверенной части графа не будут случайно пропущены.Complexity is O(V + E), as with the base DFS from 3.1.2: every vertex and edge is processed at most once thanks to `visited`. The outer loop over all t from 0 to n-1 is exactly the "disconnected graph" safeguard from 3.1.2's Gotchas section: transactions with no incoming edges from the already-checked part of the graph won't be accidentally skipped.