Топологическая сортировка

Дан ориентированный граф. Требуется упорядочить его вершины так, чтобы все рёбра вели из вершины с меньшим номером в вершину с большим номером, или определить, что это невозможно.

Начнем со случая, когда это невозможно. Заметим, что если в графе есть цикл, то топологической сортировки нет. Действительно, хотя бы одно ребро, которое как бы замыкает цикл, будет идти из вершины с большим номером назад.

Для ацикличных графов конструктивно покажем, что искомый порядок существует, построив его с помощью алгоритма обхода в глубину.

Изначально последовательность вершин пустая. Будем класть вершину, из которой нет ребер в еще нерассмотренные вершины, в конец последовательности. Заметим, что все вершины, из которых есть ребра в текущую, еще не были добавлены, а все уже рассмотренные находятся позже текущей и ребра из нее не ведут назад.

Реализуем этот алгоритм.

vector<vector<int>> g;
vector<bool> used;
vector<int> order;

void dfs(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
    order.push_back(v);
}

void main() {
    for (int v = 0; v < n; v++)
        if (!used[v])
            dfs(v);
    reverse(order.begin(), order.end());
}

Время входа и выхода dfs

Сформулируем такие понятия, как время входа (tin) и время выхода (tout), для каждой вершины. Временем будет какой-то общий счетчик операций, совершенных обходом в глубину.

vector<vector<int>> g;
int timer = 0;
vector<bool> tin, tout;

void dfs(int v) {
    used[v] = true;
    tin[v] = timer++;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
    tout[v] = timer++;
}

Компоненты сильной связности

Дадим несколько определений

Две вершины называются сильно связными, если существует путь из одной в другую и наоборот.

Множество вершин называется компонентой сильной связности, если все пары вершин в нем сильно связаны, а никакие вершины вне компоненты не связаны сильно с какой-либо вершиной в компоненте.

Граф называется сильно связным, если все его вершины сильно связны попарно.

Часто рассматривать граф с циклами неудобно, поэтому поступают следующим образом. Находят все компоненты сильной связности и строят новый граф на этих компонентах, как на вершинах. Ребрами в этом графе будут ребра из исходного графа, соединяющие вершины из разных компонент.

Легко заметить, что полученный граф будет ацикличным.

Конденсация графа

Процесс, описанный выше, называют конденсацией графа (иногда конденсацией называют сам граф на КСС). Он состоит из двух этапов: поиск компонент сильной связности, построение графа конденсации.

Для первого этапа нам понадобится доказать следующую лемму.

Лемма. Рассмотрим две различные компоненты сильной связности $A$ и $B$ такие, что есть ребро $A \rightarrow B$, тогда \(max_{a \in A} \ tout_a > max_{b \in B} \ tout_b\).

Рассмотрим 2 случая:

1. dfs сначала зашел в какую-то из его вершин $v$ в компоненте $A$

   Так как любая вершина внутри компоненты $A$ достижима, то dfs пройдет и в вершину, где начинается ребро в компоненту $B$.

   А значит, все вершины будут посещены, причем вершина $v$ будет иметь самое большое время выхода.

   Условие леммы выполняется.

2. dfs сначала зашел в какую-то из его вершин в компоненте $B$

   Тут все просто, по условию из $B$ вершины $A$ не достижимы (у нас есть только ребро $A \rightarrow B$).

   Значит, dfs выйдем из всех вершин $B$ еще до того как пойти в $A$.

На основе этого факта построим решение. Упорядочим вершин в исходном графе по убыванию времени выхода. С точки зрения кода, это то же самое, что поиск топологической сортировки.

Рассмотрим вершину с максимальным временем выхода. По лемме в компоненту, ее содержащую, не входят ребра из других компонент. Значит, все вершины, достижимые из этой по обратным ребрам, и есть компонента сильной связности.

Для оставшихся вершин, которые еще не лежат в компоненте, в порядке убывания времени выхода сделаем то же самое.

vector<vector<int>> g, rg;
vector<int> order;
vector<bool> used;
vector<int> color;
int cur_color = 0;

void dfs1(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) 
            dfs1(u);
    }
    order.push_back(v);
}

void dfs2(int v) {
    color[v] = cur_color;
    for (int u : rg[v])
        if (color[u] == 0)
            dfs2(u);
}

for (int v = 0; v < n; v++)
    for (int u : g[v])
        rg[u].push_back(v);

for (int i = 0; i < n; i++)
    if (!used[i])
        dfs1(i);

reverse(order.begin(), order.end());
for (int v : order) {
    if (color[v] == 0) {
        cur_color++;
        dfs2(v);
    }
}