Обнаружение петли в связанном графе, невозможно?

Question

Большинство примеров, которые я нашел, относятся только к отдельным спискам. Мне нужно решение для нескольких связанных списков.

Изображение проще (действительное):

Недействительным:

Какой алгоритм сможет вернуть начало цикла (B) и не сталкиваться с E? Хорошей отправной точкой было бы также узнать, есть ли вообще петля. Такие вещи, как этот, или подсчет ребер не работает (потому что не один связанный...).

Благодарю.

Answer 1

Просто проверьте, существует ли маршрут от "конца узла соединения (B)" до "начала узла соединения (C)", если да, будет создан новый цикл. Не совсем отвечает, но достаточно хорошо...