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

Задача на LCA.
Автор ilona, 12 лет назад, По-русски

Всем привет. Расскажите, пожалуйста, как решать задачу D(Цветные волшебники) в этой тренировке.

Спасибо!!

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

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

разбиваем граф на компоненты двусвязности, каждую из компонент стягиваем в одну вершину. получаем дерево на котором нужно отвечать на запросы lca. внутри любой компоненты двусвязности волшебники могут пройти так, чтобы не образовалось зелёной дороги.
то же самое, немного по-другому: находим все мосты. все мосты войдут в дерево как рёбра, выкинем их пока из основного графа, а остальные компоненты стянем каждую в одну вершину. вернем мосты в граф, у нас будет дерево, на котором надо отвечать LCA

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

    что такое компонента двусвязности?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      люди давно изобрели поисковые машины, для поиска информации в интернете. есть вершинная связность, рёберная. точного определения не скажу, но в нашем случае это короче максимальное подмножество вершин, внутри которого между двумя любыми вершинами есть два пути не пересекающихся по рёбрам. нам все такие компоненты надо найти. очевидно что способ с мостами указаный во второй правке первого сообщения сработает.

      → Ответить