Порядок установки пакетов и детект цикла через КанаPackage install order and cycle detection via Kahn's algorithm

Дано n пакетов (пронумерованы 0..n-1) и список пар `deps[i] = [a, b]`, означающий "пакет a зависит от пакета b" (b должен быть установлен раньше a). Нужно вернуть порядок установки, в котором каждый пакет ставится после всех своих зависимостей, либо пустой список, если из-за циклической зависимости корректный порядок построить невозможно.Given n packages (numbered 0..n-1) and a list of pairs `deps[i] = [a, b]`, meaning "package a depends on package b" (b must be installed before a). Return an install order in which every package comes after all its dependencies, or an empty list if a circular dependency makes a valid order impossible.

// Example 1 — валидный порядок— a valid order
n = 4, deps = [[1,0],[2,0],[3,1],[3,2]]
// output: [0, 1, 2, 3] (или [0, 2, 1, 3] — оба валидны)(or [0, 2, 1, 3] — both are valid)

// Example 2 — цикл— a cycle
n = 3, deps = [[0,1],[1,2],[2,0]]
// output: []  (0 зависит от 1, 1 от 2, 2 от 0 — установить нечего первым)(0 depends on 1, 1 on 2, 2 on 0 — nothing can be installed first)

Перевод условия ровно такой же, как в исходном примере 3.1.3: "a зависит от b" — ребро a→b. Но для порядка установки удобнее думать в терминах "b должен произойти раньше a", что как раз и есть топологический порядок — определение из 3.1.3 напрямую: для каждого ребра u→v вершина u должна стоять раньше v. Значит перед построением порядка стоит явно решить, куда направлено ребро: у нас "a зависит от b" естественно даёт ребро a→b, но для топосортировки правильнее развернуть его в b→a ("после установки b можно ставить a") — это частая точка путаницы, которую стоит проговорить вслух перед кодом, а не угадывать по ходу дела.The translation is exactly the same as in the original 3.1.3 example: "a depends on b" is an edge a→b. But for the install order, it's easier to think in terms of "b must happen before a," which is precisely the topological order definition from 3.1.3: for every edge u→v, u must come before v. So before building the order, it's worth explicitly deciding the edge direction: "a depends on b" naturally gives edge a→b, but for topological sort it's cleaner to flip it to b→a ("once b is installed, a can be installed") — a common point of confusion worth stating out loud before writing code, not guessing along the way.

Дальше — механика алгоритма Кана из 3.1.3 без изменений: считаем in-degree каждой вершины на развёрнутом графе, кладём в очередь все пакеты с in-degree 0 (у них нет неустановленных зависимостей), извлекаем их по одному, добавляем в результат и уменьшаем in-degree их "потомков" в развёрнутом графе (то есть пакетов, которые от них зависели). Если в конце размер результата меньше n — часть графа осталась недостижимой из-за цикла, и по условию задачи нужно вернуть пустой список, а не частичный порядок.From there it's Kahn's algorithm from 3.1.3, unchanged: compute each vertex's in-degree on the reversed graph, enqueue every package with in-degree 0 (no uninstalled dependencies), dequeue them one at a time, append to the result, and decrement the in-degree of their "descendants" in the reversed graph (i.e., the packages that depended on them). If the result's size ends up less than n, part of the graph was unreachable due to a cycle, and per the problem statement, an empty list must be returned, not a partial order.

class Solution {
public:
    std::vector<int> installOrder(int n, std::vector<std::vector<int>>& deps) {
        std::vector<std::vector<int>> adj(n);   // граф развёрнут: b→a// reversed graph: b→a
        std::vector<int> indeg(n, 0);
        for (auto& e : deps) {
            int a = e[0], b = e[1];      // a зависит от b// a depends on b
            adj[b].push_back(a);                // после b можно ставить a// after b, a can be installed
            indeg[a]++;
        }

        std::queue<int> q;
        for (int p = 0; p < n; ++p) if (indeg[p] == 0) q.push(p);

        std::vector<int> order;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            order.push_back(u);
            for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
        }

        if (order.size() != (size_t)n) return {};   // цикл — установка невозможна// a cycle — install is impossible
        return order;
    }
};

Сложность O(V + E), идентична базовому алгоритму Кана из 3.1.3 — построение развёрнутого графа O(E), сама сортировка O(V + E). Побочная проверка на цикл (`order.size() != n`) — не дополнительный проход, а естественное следствие того, что вершины внутри цикла никогда не достигают in-degree 0 и потому никогда не попадают в очередь.Complexity is O(V + E), identical to the base Kahn's algorithm from 3.1.3 — building the reversed graph is O(E), the sort itself is O(V + E). The cycle check as a side effect (`order.size() != n`) isn't an extra pass — it's a natural consequence of vertices inside a cycle never reaching in-degree 0 and therefore never entering the queue.