Ваш вопрос состоит в том, как определить, содержит ли данный граф
- ровно один цикл,
- , где каждый узел в цикле - это root дерева.
Хорошая новость заключается в том, что, если ваш граф связан, то если свойство (1) истинно, то и свойство (2)! Чтобы понять, почему это так, представьте себе удаление любого ребра из этого цикла. Теперь у вас есть связный граф без циклов, который является деревом. Это означает, что каждый узел, а не только узел в цикле, можно затем рассматривать как root.
Хорошая часть этого заключается в том, что существует действительно хороший алгоритм для определить, связан ли граф и содержит ли он ровно один цикл. Сначала посчитайте количество ребер в графе. Если граф действительно связан и содержит ровно один цикл, то количество ребер должно быть точно равно числу узлов. (У дерева есть еще один узел, чем ребро, и вы добавили ребро). Если это не так, то остановитесь - ответ - нет.
Оттуда вы знаете, что у вас есть правильное количество узлов и ребер. Вам просто нужно проверить, подключен ли граф, и вы можете сделать это с помощью DFS или BFS поверх графа.
Хорошая часть этого заключается в том, что если вы правильно его реализуете, время выполнения будет равно O ( n), где n - количество узлов, независимо от количества ребер. В конце концов, если вы видите более n ребер, вы можете остановить поиск.
Надеюсь, это поможет!