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

Question

Вот дерево:

1. Будет один корень.

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

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

Однако запрещено, что

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

Один запрещенный случай -

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

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

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

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

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

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

Answer 1

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

Answer 2

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