dyussenaliyev's blog

By dyussenaliyev, 8 years ago, In Russian,
Доброе время суток!
Как за О(1) выкинуть какую-то вершину из множества в СНМ-е?
Кто решил, скиньте код если можно.
Заранее спасибо!
Upd:
Итак, проблема решена. Всем спасибо!
Решение:
  • Каждую вершину i подвесить саму к себе
  • Для каждой вершины i создать фиктивную вершину i'
  • Подвесить каждую i' к i
  • Теперь, во всех операциях(union, get_set, move) использовать только фиктивные вершины
Почему нужно работать только с фиктивными вершинами?
Потому, что к ним никогда ничто не подвешивается, из-за чего нам не надо перевешивать все ссылки потомков, когда если бы делали без фиктивных вершин, надо было бы перевешивать, а это долго.
Думаю объяснил более-менее понятно.
 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it