Algorithm - 2023.2 English

procedure StronglyConnectedComponent(graph_CSR)
graph_CSC := csr2csc(graph_CSR)

for each vertex v in graph
    result(v) := -1
    color(v) := -1

while all vertexs have been labeled
    FW-coloring(graph_CSR, FW-Queue, color)
    BW-labeling(graph_CSR, graph_CSC, BW-Queue, color, result)
end while

return result

    sub procedure FW-coloring(graph_CSR, FW-Queue, color)
    rootNode := findNewRoot(FW-Queue, color)
    push rootNode into FW-Queue
    while FW-Queue is not empty
       u := pop FW-Queue
       for each edge(u, v) in graph_CSR
            if color(v) == -1 then
                color(v) = u
                push v into FW-Queue
            end if
       end for
    end while

    sub procedure BW-labeling(graph_CSR, graph_CSC, FW-Queue, BW-Queue, color, result)
    newRootNode := rootNode
    result(rootNode) := rootNode
    for v in this color region
        if indegree(v) == 0 or outdegree(v) == 0 then
            result(v) := v
        end if
    end for

    while all vertexs in this color region have been labeled
        push newRootNode into BW-Queue
        while BW-Queue is not empty
           u := pop BW-Queue
           for each edge(u, v) in graph_CSC
                if color(v) == newRootNode and result(v) == -1 then
                    result(v) = newRootNode
                    push v into BW-Queue
                end if
           end for
        end while

        if there is one more vertex which hasn't been labeled
            Re-color those vertexs which aren't labeled in last BW-BFS into rootNode
            newRootNode := FW-BFS(graph_CSR, BW-Queue, color)
            FW-BFS(graph_CSR, BW-Queue, color)
        end if
    end while