Coin Collector - Implementation

Here is the solution:

for i from 1 to numSCCs:
    dp[i] = compCoins[i]

for v in reverse(topoOrder):
    for u in compAdj[v]:
        dp[v] = max(dp[v], compCoins[v] + dp[u])

print max(dp[1..numSCCs])

Process in reverse topological order so that dp[u] for each successor u is computed before dp[v].

This runs in $O(V + E)$ time and uses $O(V)$ space.