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

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

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

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

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

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

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());
}

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

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

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

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

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

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

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

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

Процесс, описанный выше, называют конденсацией графа (иногда конденсацией называют сам граф на КСС).

Главной подзадачей является поиск компонент сильной связности. Зная их, несложно построить искомый граф.

Лемма Рассмотрим две различные компоненты сильной связности $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);
    }
}