Почему это работает
- Пока у концов ребра разные корни, ребро только соединяет две группы и цикла не даёт. Если корень уже общий, рядом с ребром есть путь, и вместе они образуют цикл.
- Цикл замыкается только тогда, когда приходит последнее в списке его ребро, поэтому первое такое ребро и есть последнее ребро цикла — то, которое нужно вернуть.
- Рёбра после него в цикл не входят, ведь цикл в графе один, поэтому прогон на нём заканчивается.
Сложность
Время O(n · h): два find на ребро глубиной с дерево, здесь до n и почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее. Память O(n) на parent.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗