Конденсация графа: различия между версиями
Debnatkh (обсуждение | вклад) (Новая страница: «== Компоненты сильной связности == Мы только что научились топологически сортировать аци...») |
KiKoS (обсуждение | вклад) м |
||
Строка 52: | Строка 52: | ||
component[v] = cnt_components; | component[v] = cnt_components; | ||
for (int u : t[v]) | for (int u : t[v]) | ||
− | if ( | + | if (component[u] == 0) |
dfs2(u); | dfs2(u); | ||
} | } |
Текущая версия на 19:42, 19 октября 2020
Компоненты сильной связности
Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? В них тоже иногда требуется найти какую-то структуру.
Для этого можно ввести понятие сильной связности.
Определение. Две вершины ориентированного графа связаны сильно (англ. 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:
- Сортируем вершины в порядке убывания времени выхода.
- Проходимся по массиву вершин в этом порядке, и для ещё непомеченных вершин запускаем dfs на транспонированном графе, помечающий все достижимые вершины номером новой компонентой связности.
После этого номера компонент связности будут топологически отсортированы.