My task is to write a function that, given a source nodes of a graph, returns the number of sink nodes (nodes with no outgoing edges) it reaches. The only access I have is to retrieve the neighbors of a node (I don't have direct access to the graph itself). The solution involves recursion, where you sum the results for all of the source neighbors by calling the same function, but ignore the visited. However, you might be concerned about hitting the maximum recursion depth, so I considered using DFS with a stack to simulate recursion.
I solved the above efficiently with DFS.
My main task:
I have multiple such source nodes, and I struggle to avoid recalculating. For instance, given the edges (1,2), (1,3), (2,4), (3,4), (5,3), source node 1 will correctly return one sink node, but to calculate the result for source node 5, there seems to be no way to avoid recalculating.
A naive solution would be to keep a unique attribute for each node that stores all the sink nodes it reaches, and then the calculation for a node would be the union of its neighbors' attributes.
My approach is as follows:
For each source node, define an empty set of visited nodes and run DFS, summing the values of all the neighbors. If a neighbor has already been visited, it is ignored in the summation. The value of each sink node is 1. However, I ended up recalculating nodes.
You might think this approach won’t update all intermediate nodes correctly, and you'd be right.
So, I also considered adding an attribute to indicate whether a node was updated correctly. The issue with this approach is that if nodes 3 and 4 were correctly updated in a previous run, you might get an incorrect result (e.g., 1 node from above incorrectly showing it has two sink nodes).
So my question is: Is there any efficient approach that avoids recalculating?
