Связность и топологическая сортировкаConnectivity & topological sort

Топологический порядок вершин DAG — это такое линейное упорядочивание, что для каждого ребра u→v вершина u стоит раньше v. Он существует тогда и только тогда, когда граф ациклический (в графе с циклом такое упорядочивание в принципе невозможно — если A→B→A, то и A должна быть раньше B, и B раньше A одновременно).A DAG's topological order is a linear ordering of vertices such that for every edge u→v, u comes before v. It exists if and only if the graph is acyclic (in a graph with a cycle, such an ordering is fundamentally impossible — if A→B→A, then A must come before B and B before A at the same time).

Алгоритм Кана строит порядок итеративно, без рекурсии: посчитать in-degree каждой вершины, положить в очередь все вершины с in-degree = 0 (у них нет невыполненных зависимостей), затем повторно извлекать вершину из очереди, добавлять в результат и уменьшать in-degree всех её соседей — если чей-то in-degree стал 0, он тоже добавляется в очередь. Если в конце обработаны не все вершины — в графе есть цикл (побочный эффект: Кан заодно детектирует циклы).Kahn's algorithm builds the order iteratively, without recursion: count each vertex's in-degree, enqueue every vertex with in-degree 0 (no unmet dependencies), then repeatedly dequeue a vertex, append it to the result, and decrement the in-degree of all its neighbors — if any neighbor's in-degree hits 0, enqueue it too. If not all vertices are processed by the end, the graph has a cycle (a side effect: Kahn's algorithm detects cycles for free).

std::vector<int> topoSort(int n, const std::vector<std::vector<int>>& adj) {
    std::vector<int> indeg(n, 0), order;
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) indeg[v]++;
    std::queue<int> q;
    for (int u = 0; u < n; ++u) if (indeg[u] == 0) q.push(u);
    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) throw std::runtime_error("cycle detected");
    return order;
}

Компонента сильной связности (SCC) — максимальное подмножество вершин ориентированного графа, где из любой вершины достижима любая другая внутри этого подмножества. Свёртка каждой SCC в одну "суперверщину" всегда превращает исходный ориентированный граф в DAG — это ключевой факт, который делает SCC полезными: сложная структура с циклами разбивается на простую ациклическую структуру связей между блоками.A strongly connected component (SCC) is a maximal subset of a directed graph's vertices where every vertex can reach every other vertex within that subset. Collapsing each SCC into a single "super-vertex" always turns the original directed graph into a DAG — this is the key fact that makes SCCs useful: a complex structure full of cycles decomposes into a simple acyclic structure of connections between blocks.

Алгоритм Косарайю — концептуально простой: DFS на исходном графе, запоминая порядок выхода из вершин (tout); затем DFS на транспонированном графе (все рёбра развёрнуты), запускаемый от вершин в порядке убывания tout — каждое дерево этого второго обхода и есть одна SCC. Алгоритм Тарьяна находит SCC за один проход DFS (без построения транспонированного графа), используя low-link значения (то же понятие, что и для мостов в 3.1.2) и явный стек — вершина является "корнем" своей SCC, если её `low` равен её собственному `tin`.Kosaraju's algorithm is conceptually simple: DFS on the original graph, recording vertex exit order (tout); then DFS on the transposed graph (every edge reversed), launched from vertices in decreasing tout order — each tree of this second traversal is one SCC. Tarjan's algorithm finds SCCs in a single DFS pass (no transposed graph needed), using low-link values (the same concept as for bridges in 3.1.2) and an explicit stack — a vertex is the "root" of its SCC if its `low` equals its own `tin`.