Используем модифицированный алгоритм Флойда - алгоритм Уоршалла.
Или транзитивное замыкание матрицы.
Вход - булева матрица смежности,
(1 есть ребро 0 нету)
как и в алгоритме
флойдакаждый элемент матрицы вычисляется по формуле, для данного случая такой:
A
k[i,j]=A
k-1[i,j] or (A
k-1[i,k] and A
k-1[k,j])
В результате получим матрицу, и надо будет проверить ее на наличие нулевых элементов, если нету то граф связан.
Можно использовать и прямо алгоритм Флойда... алгоритмическая сложность одна и та же...
Тогда для проверки на связанность надо будет проверить нет ли в результате бесконечных путей.