Небольшая модификация алгоритма обхода в глубину позволяет проверить связность неориентированного графа.
Один из вариантов Идея алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
string color[]; //изначально массив color заполнен значениями white.
int count = n; //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected() dfs(0) string color[]; //запуск от изначально массив color заполнен значениями white. какой-то вершины if(int count == 0) return truen; else return false //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected() dfs(0); //запуск от какой-то вершины if(count == 0) return true; else return false; int dfs(int u) //процедура обхода в глубину. запуск от номера вершины for(v: uv - ребро) if(color[v] == white) dfs(v); color[u] = black; count--;
