Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Common Ancestor in a Directed Acyclic Graph (DAG)
Автор zeref_dragoneel, история, 9 лет назад, По-английски

I need to find all pairs of nodes which have a common ancestor in a DAG in O(n^2 + m) time. I can use O(n^2 memory).

Please suggest a method to do this ?

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

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

I think we can consecutively choose all nodes, run dfs from the current node and then for those vertices having parent the current node (say this is the set of vertices K) we want to count in how many ways we can choose two vertices from set V (the vertices of the initial graph) such that both of them have an ancestor from set K and their ancestors are different. It makes O((N+M)*N) time and O(N) additional memory. But I am not sure if this will work, once I tried such problem with this strategy and didn't get AC :(

UPD: The complexity is actually O((N+M)*N).

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

    I did not get exactly what are you saying ?

    or if I got u right, then the aalgo will take O(n^2 m) time not O(n^2 + m)

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

      Oops, I am sorry, the complexity is O((N+M)*N). Will this be enough or no? The problem I was trying to solve had constraints N,M<=10^4 so this was enough but I got WA, still I don't see a mistake :)

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

So you can count the number of pair which do not have common ancestor and then decrease it from n*(n-1)/2 (n=number of nodes).

Let's say you want to count this number for node x.You make a dfs to see all his ancestors(nodes from which u can reach x).Then from all those ancestor make a single bfs to see what other nodes u can reach.(in queue u put first all ancestors,so actually complexity will be O(n+m)) After that,for all nodes that are nodes that are not visited(by any possible ancestor of x),it means they do not have a common ancestor :)

Complexity O((n+m)*n) memory O(n+m);

→ Ответить