Блог пользователя KaiZeR

Как улучшить dsu?
Автор KaiZeR, 13 лет назад, По-русски

Подскажите пожалуйста возможно ли в системе непересекающихся множеств реализовать разъединение множеств не теряя при этом выигрыша во времени (например не отказываясь от использования эвристики сжатия путей).

Теги dsu
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

можно делать откаты: запоминать изменения, а затем делать их в обратном порядке.

почитай вот этот тред, там в моих сообщения объясняется как это делать. и там же есть ссылка на код

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
У меня одного оформление поста кривое показывается (комментарии справа от серой линии)?
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Еще есть реализация DSU на списках. при слиянии множеств запихивваешь содержимое меньшего списка в больший. крускал при такой реализицаии в худшем случае за N Log N заботает. Вместо списков можно юзать мапы/хешмапы, тогда можно будет за размер меньшего подмножества расщеплять множества произвольным образом, а не откатываясь к предыдущему состоянию.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Следующая задача легко решается за время O(log n) на операцию. У нас есть n вершин, мы можем добавлять ребра между ними и удалять, но так, чтобы все время был лес. Еще надо уметь отвечать на запросы "в одной ли компоненте связности лежат две заданные вершины". Вроде, это то, что нужно?
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "не теряя при этом выигрыша во времени"
    Видимо требуется именно решение за O(1) 
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Когда это вы последний раз видели DSU за O(1)? Когда следующий раз увидите - киньте плз ссылку, это ведь сверхпрорыв в математике будет (особенно если учесть, что есть нижние оценки) :)
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вот недавно профессор из Принстона чуть такой прорыв не произвел!
        → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        DSU работает за O(a(n)), a(n) не принимает значений больше четырех для всех мыслимых n. Чем не константа? 
        → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится
          Перебор работает за 2n, 2n не принимает значений больше 2264 для всех n, влезающих в long long. Чем не константа? :trollface:
          → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
           Тем, что не константа.
          → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Ну а по теме - см. нижние оценки здесь.
          → Ответить
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Хм... Ну да, нижние меньше похожи на константу. Всё, уговорили =)
            → Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Link-cut trees нынче зачислены в разряд "легко и доступно каждому"? :) Или есть что-то более лёгкое?
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится
      Link-cut trees не нужны. Идея очень простая: давайте хранить каждую компоненту в виде списка вершин, полученного обходом в глубину. Тогда все нужные операции выражаются через split/merge, что позволяет реализовать их с помощью любого сбалансированного дерева.
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Действительно очень простая, ну и дела... Большое спасибо за новое знание ;)
        → Ответить