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

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

Определение. Две вершины ориентированного графа связаны сильно (англ. strongly connected), если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.

Понятно, что такое отношение транзитивно: если $a$ и $b$ сильно связны, и $b$ и $c$ сильно связны, то $a$ и $c$ тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.

Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.

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

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

Если мы уже знаем, какие вершины лежат в каждой компоненте сильной связности, то построить граф конденсации несложно: нужно провести некоторые манипуляции со списками смежности, заменив для всех ребер номера вершин номерами их компонент, а затем объединив списки смежности для всех вершин каждой компоненты. Поэтому сразу сведем исходную задачу к нахождению самих компонент.

Лемма. Запустим dfs. Пусть $A$ и $B$ — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро $A \to B$. Тогда:

Доказательство. Рассмотрим два случая, в зависимости от того, в какую из компонент dfs зайдёт первым.

Пусть первой была достигнута компонента $A$, то есть в какой-то момент времени dfs заходит в некоторую вершину $v$ компоненты $A$, и при этом все остальные вершины компонент $A$ и $B$ ещё не посещены. Но так как по условию в графе конденсаций есть ребро $A \to B$, то из вершины $v$ будет достижима не только вся компонента $A$, но и вся компонента $B$. Это означает, что при запуске из вершины $v$ обход в глубину пройдёт по всем вершинам компонент $A$ и $B$, а, значит, они станут потомками по отношению к $v$ в дереве обхода, и для любой вершины $u \in A \cup B, u \ne v$ будет выполнено $tout_v] > tout_u$, что и утверждалось.

Второй случай проще: из $B$ по условию нельзя дойти до $A$, а значит, если первой была достигнута $B$, то dfs выйдет из всех её вершин ещё до того, как войти в $A$.

Из этого факта следует первая часть решения. Отсортируем вершины по убыванию времени выхода (как бы сделаем топологическую сортировку, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины в сортировке. В эту компоненту точно не входят никакие рёбра из других компонент — иначе нарушилось бы условие леммы, ведь у первой вершины $tout$ максимальный. Поэтому, если развернуть все рёбра в графе, то из этой вершины будет достижима своя компонента сильной связности $C^\prime$, и больше ничего — если в исходном графе не было рёбер из других компонент, то в транспонированном не будет ребер в другие компоненты.

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

vector<int> g[maxn], t[maxn];
vector<int> order;
bool used[maxn];
int component[maxn];
int cnt_components = 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) {
    component[v] = cnt_components;
    for (int u : t[v])
        if (component[u] == 0)
            dfs2(u);
}


// в содержательной части main:

// транспонируем граф
for (int v = 0; v < n; v++)
    for (int u : g[v])
        t[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 (component[v] == 0)
        dfs2(v), cnt_components++;

TL;DR:

1. Сортируем вершины в порядке убывания времени выхода.
2. Проходимся по массиву вершин в этом порядке, и для ещё не помеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компоненты связности.

После этого номера компонент связности будут топологически отсортированы.