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

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-connectivity-mst/implementation-checkposts

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

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

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-connectivity-mst/implementation-checkposts

Repovive

Implementation - Checkposts - Mixed Practice: Connectivity & MST | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Checkposts

SCC + cost minimization

Here is the SCC-based implementation:

function checkposts(n, costs, adj):
    sccId = tarjanSCC(adj)
    numSCCs = max(sccId) + 1

    // For each SCC, find min cost and count
    minCost = array of size numSCCs, all infinity
    count = array of size numSCCs, all 0

    for i from 0 to n - 1:
        c = sccId[i]
        if costs[i] < minCost[c]:
            minCost[c] = costs[i]
            count[c] = 1
        else if costs[i] == minCost[c]:
            count[c] = count[c] + 1

    totalCost = 0
    ways = 1
    for c from 0 to numSCCs - 1:
        totalCost = totalCost + minCost[c]
        ways = (ways * count[c]) mod (10^9 + 7)

    print totalCost, ways

Time: $O(V + E)$ . Space: $O(V)$ .