Coin Collector - Implementation

function coinCollector(n, coins, edges):
    // Step 1: Find SCCs (Kosaraju or Tarjan)
    sccs = findSCCs(n, edges)

    // Step 2: Condense graph
    sccCoins = array of sums for each SCC
    sccAdj = adjacency list for condensed DAG

    // Step 3: DP on DAG
    // dp[i] = max coins reachable ending at SCC i
    dp = array of 0s
    for each SCC in topological order:
        dp[scc] = max(dp[scc], sccCoins[scc])
        for each neighbor in sccAdj[scc]:
            dp[neighbor] = max(dp[neighbor], dp[scc] + sccCoins[neighbor])

            return max(dp)

Time: $O(V + E)$ for SCCs and DP.

Space complexity is $O(V)$ for the data structures used.