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

Нахождение количества пар вершин, у которых есть хотя бы один общий предок.
Автор Loud_Scream, история, 9 лет назад, По-русски

Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?

Теги dfs, bfs
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

А можно ссылку на задачу?

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

    http://www.e-olymp.com/ru/problems/3298

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

      Мне кажется, что ограничения и TL намекают на решение за VE. Сожмем компоненты сильной связности и дальше решим задачу для ациклического графа. Насчитаем динамику dp[a][b] — правда ли что (a,b) — хорошая пара. 1) Если из a достижима b или наоборот, то пара хорошая (эти пары можно найти, запустив dfs из каждой вершины) 2) Иначе пара хорошая, только если есть вершина p, такая что dp[a][p]=true и есть ребро (p->b). Суммарно таких переходов Е

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

        А после, получая ответ, нужно для каждой сильной компоненты связности умножить на ее размер?

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

        А почему критерием является именно существование ребра между b и p, а не равенство dp[b][p] = true?

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

          Ну пусть такая вершина есть, и она не а и не b. Посторем пути из k в а и из k в b. Очевидно, что последнее ребро на пути из k в b входит в b.

          → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А, не, фигню написал.

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

Это задача с опенкапа гран-при Украины Associated Vertices.

Нужно сделать два графа — первый с исходным набором ребер, второй — с обратным.

Затем из каждой вершины нужно запустить бфс по состояниям. Состояние (ver, last) будет говорить, а правда ли что можно прийти в вершину ver, где last — граф, по которому мы ходили. Если мы ходили по обычному, то если есть ребра в обратном — можно по ним ходить. Если последний раз мы ходили по обратным ребрам — то только по ним и ходим.

Code here.

→ Ответить