likecs's blog

A DAG Problem
By likecs, history, 8 years ago, In English

A was thinking about a DAG problem. It goes as follows:

You are given a directed acyclic graph with N nodes and M edges. Every vertex has a number associated with it, let us call it A[i]. The power of every vertex is defined as the sum of values written on every vertex reachable from it. We are given Q queries. In each query we need to find the power of a given vertex.

For example, Let N = 5, M = 5 and the value of A = {2, 3, 1, 4, 2}. (Assume 1-based indexing). Let the edges be {(2, 1), (3, 1), (4, 2), (4, 3), (3, 5)}, where (x, y) means there is directed edge from x to y.

So, querying for vertex 4, gives a answer of (2 + 3 + 1 + 4 + 2) = 12, as every vertex is reachable from it, while for vertex 3, it gives answer as (2 + 3 + 2) = 7 as only {1, 3, 5} are reachable from it.

The brute force solution is to perform dfs/bfs in every query. If possible, can you please provide an efficient algorithm for this. (I was thinking about some kind of precomputation using topological sort, but ended but added some values more than once.)

Thank you.

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this problem from some online judge?

Provide link if possible.

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

    There is no specific problem on online judge. But this problem is quite similar to it after compressing the SCC's and doing the above operation as stated.

    → Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it -17 Vote: I do not like it

Embarrassing solution in EDIT :|

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

I don't see why you cannot do DP on the DAG and cache the answers for every node. The recursion looks like:

for child of node i:
    dfs(child)
    sum[i] += sum[child]

then you just read the sum value at a node you need to query.

Have I misunderstood the problem?

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

    For a very simple graph like this:

    N = 3, edges between 1 - 2, 1 - 3 and 2 - 3. If your for loop traverses nodes in the order 3, 2 and 1, then A3 will get added twice in answer of 1.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Of course! How embarrassing. Thank you.

      → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

An easier task of the very same problem cannot be solved better than O(n * m * bitset), so i doubt the complexity will get any better here.

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

    Oh shit! Why won't this work?

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

    I think O(n * m * bitset) overestimates the actual complexity by a fair amount. That if not bitset = 1 / 32

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +59 Vote: I do not like it

      Awwww, my smart boy :* That's why I wuv u.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yes, you are right. I thought it would be more suggestive as bitset because you may also get lower constants depending on the implementation.

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

Misunderstood the problem >_<

→ Reply