zeref_dragoneel's blog

Common Ancestor in a Directed Acyclic Graph (DAG)
By zeref_dragoneel, history, 9 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 :)

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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);

→ Reply