Доброе время суток!
Как за О(1) выкинуть какую-то вершину из множества в СНМ-е?
Задача "А" с Rujia Liu's Present 3 contest.
Кто решил, скиньте код если можно.
Заранее спасибо!
Upd:
Итак, проблема решена. Всем спасибо!
Решение:
- Каждую вершину i подвесить саму к себе
- Для каждой вершины i создать фиктивную вершину i'
- Подвесить каждую i' к i
- Теперь, во всех операциях(union, get_set, move) использовать только фиктивные вершины
Почему нужно работать только с фиктивными вершинами?
Потому, что к ним никогда ничто не подвешивается, из-за чего нам не надо перевешивать все ссылки потомков, когда если бы делали без фиктивных вершин, надо было бы перевешивать, а это долго.
Думаю объяснил более-менее понятно.
Comments (0)
