Given a directed graph, suppose we want to find the number of reachable nodes from each node of the graph then what is the best way to solve this problem ??
One obvious way to solve it is doing dfs from every node of the graph and counting how many nodes are getting visited, but the problem with this approach is that it is O(n^2) where n is the number of nodes in the graph
Then i thought of maybe if we can store at each node how many nodes are reachable and when queried give the answer based on the values of the neighbouring nodes but this will not be able to handle the case of overcounting as in the graph below.
So how to solve this ?