Что делает: bruh

Где используется: конденсация графа

Общая идея:

Запустить DFS и в мейне до начала каждой рекурсии увеличивать количество компонент

Реализация:

// псевдокод писала Я так что чекните если что не так!

int main() {
	for u из G(V) do
		if (!u.visited) { // запускаем DFS для всех не пройденных вершинок
			current_components_num++ // увеличиваем число компонент после
															// каждого выхода из DFS
			DFS(u)
		}
}

void DFS(int u) {
	u.visited = true // помечаем, что вершинку посетили
	u.component = current_components_num // "сжимаем" вершинки в одну
		for v из G(V) do
			if !v.visited
				DFS(v)
}

Просто запустить дфс и при окончании каждого увеличивать число компонент на одну в мейне

‼ Особенности поиска компонент связности в неориентированном графе:

1. ну, лол.

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