title: How to count all reachable nodes in a directed graph?
body: <p>There is a directed graph (which might contain cycles), and each node has a value on it, how could we get the sum of reachable value for each node. For example, in the following graph: </p>
  
  <p><a href="https://i.stack.imgur.com/Z2bqd.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Z2bqd.png" alt="directed graph"></a></p>
  
  <p>the reachable sum for node 1 is: 2 + 3 + 4 + 5 + 6 + 7 = 27</p>
  
  <p>the reachable sum for node 2 is: 4 + 5 + 6 + 7 = 22</p>
  
  <p>.....</p>
  
  <p>My solution: To get the sum for all nodes, I think the time complexity is O(n + m), the n is the number of nodes, and m stands for the number of edges. DFS should be used,for each node we should use a method recursively to find its sub node, and save the sum of sub node when finishing the calculation for it, so that in the future we don't need to calculate it again. A set is needed to be created for each node to avoid endless calculation caused by loop. </p>
  
  <p>Does it work? I don't think it is elegant enough, especially many sets have to be created. Is there any better solution? Thanks.</p>