Задача. Найти подграф и т.д.

[Null]

Насколько я помню проверка графа на двухсвязность делаться за 1 обход в глубину.

[useroto]

Null
а по подробней можно

[Null]

Ошибся у вас нужна реберная двусвязность: надо просто перебрать все ребра и проверить: при удалении любого ребра связность должна сохранится.