Что делает: сжимает граф в граф компонент (все вершинки компоненты сжимаются в одну “большую” вершинку и между ними только мосты)

Что использует: нахождение компонент сильной связности или нахождение компонент связности в неориентированном графе (пососи)

Общая идея:

Транспонировать граф (направления рёбер меняются на обратные) → G’, а затем запустить два (разных) DFS для обоих графов

Подробное доказательство:

1. При транспонировании графа, G и G’ имеют одни и те же сильно связные компоненты. DFS_1 для G запускается для вычисления времен выхода каждой из вершинок: компонента связности с вершиной, у которой время выхода больше всех, не имеет ребёр, ведущих в другие компоненты в транспонированном графе (и естественно является компонентой, в которую никто не входит в исходном графе).
   

2. DFS_2 для G’ запускается в порядке убывания выхода вершин, и с помощью этого DFS_2 находим уже сами компоненты сильной связности, т.к. при запуске вершины с максимальным временем выхода в обратном графе мы попадем в компоненту, из которой нет пути в другую компоненту. Затем как бы “удаляем” (игнорируем) все пройденные вершины, и идем по новой компоненте.
   

Реализация:

1. DFS(G) для вычисления времен завершения для каждой вершины
2. Вычисление G' (транспонированный граф)
3. DFS(G') в порядке убывания времени выхода вершинок

vector<vector <int>> graph, reverseGraph // граф, трансграф
vector<int> timeOut // время выхода вершин в порядке возрастания

int main() {
	1. for u из G(V) do
		if (!u.visited)
			DFS_1(u) // поиск времени выхода вершин
  2. // трансграф + реверс timeOut чтобы вершины были в порядке убывания
	3. for u из G(V) do
				u.visited = false // очищаем вершины от посещения
		 for u из G(V) do
				v = timeOut[u]
				if (!u.visited) {
					DFS_2(v)
					current_components_num++ // увеличиваем число компонент 
																	// после завершения каждого DFS
				}
			
	4. for u из G(V) do
				cout << u.component << " " // выводим для каждой вершинки компоненту
}

DFS_1(int u) {
	u.visited = true;
	for v из G(V) do
			if v.visited == false
				DFS_1(v)
	timeOut.push_back(u) // закидываем вершины в порядке выхода
}

DFS_2(int u) {
	u.visited = true; // еще раз помечаем пройденность, т.к. в мейне очищаем от цвета
	u.component = current_components_num // по сути конденсация
	for v из G(V) do
			if v.visited == false
				DFS_2(v)
}

‼ Особенности конденсации графа:

1. приведенный алгоритм робит только для ориентированных графов! в неор. графах невозможно построить граф компонент, или он будет несвязным. тогда используется поиск компонент связности в неор. графе через один DFS

Визуализация: этим я займусь чуть попозже