Implementation - Checkposts

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)$.