Помогите с задачей!

[Cr1stal]

Построить детерминированную машину Тьюринга, выписывающую за полиномиальное время все компоненты связности неориентированного графа.
Какой здесь алгоритм действий????

[Xaositect]

Ну как.
Берем вершину, добавляем к ней все смежные с ней, потом смежные со смежными и т. д. пока не станет так, что не сможем ничего добавить - это получится одна компонента связности.
Если еще остались вершины, берем одну из них и так же строим ее компоненту связности.
И так далее, пока граф не кончится.

[Cr1stal]

а подробней немного..

[Xaositect]

А подробности зависят от того, как у Вас вводились машина Тьюринга и кодировка графов в строки.