Использование обхода в глубину для проверки связности

Задача

Дан неориентированный граф G и две вершины U и V. Необходимо проверить существует ли путь из вершины U в вершину V по рёбрам графа G.

Алгоритм

Небольшая модификация алгоритма обхода в глубину. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины U и проверять при каждом посещении вершины, не является ли она искомой вершиной V. Так как в первый момент времени все пути в графе "белые", то если вершина V и была достижима из U, то по Лемма о белых путях в какой-то момент времени мы зайдём в вершину V, чтобы её покрасить.

Алгоритм

Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности. Работает алгоритм за O(M + N).

Псевдокод

string color[];         //изначально массив color заполнен значениями white.
int count = n;          //счётчик количества вершин; изначально равен количеству вершин в графе
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--;