#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-graphs/coin-collector-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-advanced-graphs/coin-collector-implementation

Repovive

Coin Collector - Implementation - Mixed Practice: Advanced Graphs | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Coin Collector - Implementation

Code walkthrough.

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.