Как проверить, есть ли круг в дереве?

Question

Вот такое дерево:

1. Там будет один корень.

2. Каждый узел дерева имеет ноль или более дочерних элементов.

3. Допускается, что два узла указывают на один и тот же дочерний узел.Скажем, как узел A , так и узел B имеют дочерний C.

Однако запрещается, чтобы,

Узел A является потомком узла B, и Узел B является потомком узла A.

Одним из запрещенных случаев является

Узел A имеет дочерний узел C и Узел D,

Оба узла C и D имеют дочерний узел E,

Узел E имеет дочерний элемент A.

Вопрос в том, как быстрее всего определить этот круг?

Обновить:Я понимаю, что это делается для того, чтобы найти любой цикл в ориентированном графе.Только сейчас мне удалось придумать решение, похожее на алгоритм Тарьяна.

Спасибо за комментарии.

Answer 1

Сделайте Поиск в глубину Сначала сквозь дерево.Если в какой-то момент вы обнаружите узел, который уже находится в вашем стеке обратного отслеживания, там будет круг.

Answer 2

круги можно найти, используя 2 указателя и продвигая их с разными интервалами.В конце концов указатели совпадут, указывая на цикл, или "более быстрый" цикл достигнет своего завершения.Однако обычно этот вопрос задается связанным спискам, а не деревьям.