sidef-scripts/Math/kosaraju_s_algorithm.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Kosaraju
#

func korasaju(Array g) {
    # 1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
    var vis = g.len.of(false)
    var L   = []
    var x   = g.end
    var t   = g.len.of { [] }

    # Recursive
    func visit(u) {
        if (!vis[u]) {
            vis[u] = true
            g[u].each {|v|
                visit(v)
                t[v] << u
            }
            L[x--] = u
        }
    }

    # 2. For each vertex u of the graph do visit(u)
    g.range.each {|u|
        visit(u)
    }

    var c = []

    # 3. Recursive subroutine:
    func assign(u, root) {
        if (vis[u]) {
            vis[u] = false
            c[u] = root
            t[u].each {|v|
                assign(v, root)
            }
        }
    }

    # 3. For each element u of L in order, do assign(u, u)
    L.each {|u|
        assign(u, u)
    }

    return c
}

var g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
var c = korasaju(g)
say c

assert_eq(c, [0, 0, 0, 3, 3, 5, 5, 7])