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

$ curl repovive.com/roadmaps/graph-theory/strongly-connected-components/tarjan-implementation

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

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

$ curl repovive.com/roadmaps/graph-theory/strongly-connected-components/tarjan-implementation

Repovive

Tarjan - Implementation - Strongly Connected Components | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Tarjan - Implementation

(C++ code)

Here is Tarjan:

function tarjan(v):
    disc[v] = low[v] = timer
    timer = timer + 1
    st.push(v)
    onStack[v] = true

    for u in adj[v]:
        if disc[u] == -1:
            tarjan(u)
            low[v] = min(low[v], low[u])
        else if onStack[u]:
            low[v] = min(low[v], disc[u])

    if low[v] == disc[v]:
        while st.top() != v:
            scc[st.top()] = comp
            onStack[st.top()] = false
            st.pop()
        scc[v] = comp
        onStack[v] = false
        comp = comp + 1
        st.pop()

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