Находятся ли элементы в одной компоненте
Система непересекающихся множеств (DSU)
Очень легкая
Есть n элементов (пронумерованных от 0 до n-1) и список пар unions - какие элементы объединены в одну группу. Используя систему непересекающихся множеств (Union-Find), определите, находятся ли элементы x и y в одной компоненте связности.
Сигнатура функции
same_component(n: int, unions: list[list[int]], x: int, y: int) -> bool
Примеры
| Вход | Ожидаемый результат |
|---|
| [5, [[0, 1], [1, 2], [3, 4]], 0, 2] | true |
| [5, [[0, 1], [1, 2], [3, 4]], 0, 4] | false |
1решили
1пытались
100%успешность
Войдите, чтобы решить →