Конденсация

Материал из Algocode wiki
Версия от 21:22, 20 декабря 2019; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Дан ориентированный граф $G$, множество вершин которого $V$ и множество рёбер — $E$. Конденсацией назовем сжатие каждой компоненты сильной связности в одну вершину. Каждой вершине графа конденсации соответствует компонента сильной связности графа $G$, а ориентированное ребро между двумя вершинами $C_i$ и $C_j$ графа конденсации проводится, если найдётся пара вершин $u \in C_i, v \in C_j$, между которыми существовало ребро в исходном графе, т.е. $(u,v) \in E$.

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

Теорема

Запустим DFS. Пусть $C$ и $C^\prime$ — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро $(C,C^\prime)$. Тогда $\max\limits_{c\in C}(\space{\rm tout}[c]) > \max\limits_{c^\prime\in C^\prime}({\rm tout}[c^\prime])$.

При доказательстве возникают два принципиально различных случая в зависимости от того, в какую из компонент первой зайдёт обход в глубину:

Первой была достигнута компонента $C$. Это означает, что в какой-то момент времени обход в глубину заходит в некоторую вершину $v$ компоненты $C$, при этом все остальные вершины компонент $C$ и $C^\prime$ ещё не посещены. Но, т.к. по условию в графе конденсаций есть ребро $(C,C^\prime)$, то из вершины $v$ будет достижима не только вся компонента $C$, но и вся компонента $C^\prime$. Это означает, что при запуске из вершины $v$ обход в глубину пройдёт по всем вершинам компонент $C$ и $C^\prime$, а, значит, они станут потомками по отношению к $v$ в дереве обхода в глубину, т.е. для любой вершины $u \in C \cup C^\prime, u \ne v$ будет выполнено ${\rm tout}[v] > {\rm tout}[u]$, ч.т.д.

Обратный случай рассматривается проще, из $C^\prime$ нельзя добраться до $C$, а следовательно доказано.

Алгоритм

Из этого и следует первая часть решения - давайте отсортируем вершины по убыванию времени выхода (будто топсорт, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины, назовем ее $C^\prime$. В эту компоненту точно нет никаких рёбер из других компонент (иначе $\max\limits_{c\in C}(\space{\rm tout}[c]) > \max\limits_{c^\prime\in C^\prime}({\rm tout}[c^\prime])$, а первая вершина - это вообще-то максимум времени выхода). Поэтому если мы развернем все ребра, то из этой вершины все еще будет достижима своя компонента сильной связности $C^\prime$, и больше точно ничего - если раньше не было ребер из других компонент, то после разворота ребер не стало ребер в другие компоненты.

Так что второй шаг такой - разворачиваем ребра, запускаем DFS в таком порядке, ищем компоненты связности как в обычном графе. Попутно можно строить и граф конденсации.

Реализация

 1 vector<int> g[N], gr[N];
 2 bool used[N];
 3 vector<int> order, component;
 4  
 5 void dfs1(int v) {
 6     used[v] = true;
 7     for (int i = 0; i < g[v].size(); i++) {
 8         if (!used[g[v][i]]) {
 9             dfs1(g[v][i]);
10         }
11     }
12     order.push_back (v);
13 }
14  
15 void dfs2(int v) {
16     used[v] = true;
17     component.push_back(v);
18     for (int i = 0; i < gr[v].size(); i++) {
19         if (!used[gr[v][i]]) {
20             dfs2(gr[v][i]);
21         }
22     }
23 }
24  
25 int main() {
26     for (;;) {
27         g[a].push_back(b);
28         gr[b].push_back(a);
29     }
30     for (int i = 0; i < n; i++){
31         if (!used[i]) {
32             dfs1(i);
33         }
34     }
35     for (int i = 0; i < n; i++) {
36         used[i] = 0;
37     }
38     reverse(order.begin(), order.end());
39     for (int i = 0; i < n; i++) {
40         int v = order[i];
41         if (!used[v]) {
42             dfs2 (v);
43         }
44     }
45 }

Оценка времени работы

Так как мы честно посмотрим все ребра и вершины в DFS, то время работы программы будет - $O(N + M)$



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin