Лишнее ребро, создающее цикл
Система непересекающихся множеств (DSU)
Средняя
Дан список рёбер edges неориентированного графа, который изначально был деревом из n вершин (занумерованы с 1), но получил одно лишнее ребро, образовавшее цикл. Используя Union-Find, найдите это лишнее ребро (если их несколько - верните то, что встречается в списке последним).
Сигнатура функции
find_redundant_connection(edges: list[list[int]]) -> list[int]
Примеры
| Вход | Ожидаемый результат |
|---|
| [[[1, 2], [1, 3], [2, 3]]] | [2, 3] |
| [[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]] | [1, 4] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →