Нахождение связанных компонентов

Условие

Задан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами. Требуется найти в нём все связные компоненты — группы вершин такие, что внутри группы из каждой вершины можно добраться до любой другой, а между разными группами пути не существует.

Решение

Для решения этой задачи можно использовать DFS или BFS.

Фактически мы выполняем серию запусков DFS/BFS:

первый запуск стартует из первой вершины и находит все вершины первой связной компоненты;
затем берём первую ещё не посещённую вершину и запускаем обход из неё — так находим вторую компоненту;
и так далее, пока не будут посещены все вершины.

Общее время работы алгоритма: $O(n + m)$ .