Матрица смежности

[CBst]

Здравствуйте.

Как определить по матрице смежности, является ли граф - лесом?
В интернете не нашел, может книжка какая есть?

[Sonic86]

Лес - это граф, компоненты связности которого - деревья. Просто ищите компоненты связности и проверяйте, являются ли они деревьями (можно взять алгоритм проверки графа на деревянность и допилить его с учетом нескольких компонент связности). И будет время $O(n)$ - меньше все равно нельзя + $O(n)$ памяти.
upd: насчет времени $O(n)$ не уверен.

[CBst]

Хорошо, как проверить на древесность я знаю, но как найти подматрицу для каждой компоненты связности?

[Sonic86]

CBst в сообщении #705347 писал(а):

как найти подматрицу для каждой компоненты связности?

Это стандартная проблема и решения у ней стандартные и простые. Вы вполне можете придумать ответ на этот вопрос сами.