Конденсация: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 73: | Строка 73: | ||
==Оценка времени работы== | ==Оценка времени работы== | ||
− | Так как мы честно посмотрим все ребра и вершины в | + | Так как мы честно посмотрим все ребра и вершины в DFS, то время работы программы будет - $O(N + M)$ |
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 18: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