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.
Is this problem from some online judge?
Provide link if possible.
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.
Embarrassing solution in EDIT :|
Embarrassing analysis of the embarrassing solution above in EDIT. :|
Your 2nd part is not clear and might be wrong. You can test your solution here : http://www.spoj.com/problems/DAGCNT2/ and tell us if it passes :)
It is wrong! Sorry, don't know why I say stuff with this confidence :P
I don't see why you cannot do DP on the DAG and cache the answers for every node. The recursion looks like:
then you just read the sum value at a node you need to query.
Have I misunderstood the problem?
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.
Of course! How embarrassing. Thank you.
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.
Oh shit! Why won't this work?
I think O(n * m * bitset) overestimates the actual complexity by a fair amount. That if not bitset = 1 / 32
Awwww, my smart boy :* That's why I wuv u.
Yes, you are right. I thought it would be more suggestive as bitset because you may also get lower constants depending on the implementation.
Misunderstood the problem >_<