Конденсация
Задача
Дан ориентированный граф $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$, а следовательно доказано. =='"`UNIQ--h-2--QINU`"'Алгоритм== Из этого и следует первая часть решения - давайте отсортируем вершины по убыванию времени выхода (будто топсорт, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины, назовем ее $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 в таком порядке, ищем компоненты связности как в обычном графе. Попутно можно строить и граф конденсации. =='"`UNIQ--h-3--QINU`"'Реализация== '"`UNIQ--syntaxhighlight-00000000-QINU`"' =='"`UNIQ--h-4--QINU`"'Оценка времени работы== Так как мы честно посмотрим все ребра и вершины в BFS, то время работы программы будет - $O(N + M)$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin