A DAG Problem

Правка en1, от likecs, 2016-12-08 00:24:04

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.

Теги dag, queries

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский likecs 2016-12-08 00:24:04 1109 Initial revision (published)