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

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

Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? В них тоже иногда требуется найти какую-то структуру.

Для этого можно ввести понятие сильной связности.

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

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

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

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

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

Лемма. Запустим dfs. Пусть \(A\) и \(B\) — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро \(A \to B\). Тогда\[ \max\limits_{a \in A}(tout_a) > \max\limits_{b\in B}(tout_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);

TL;DR:

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

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