47 lines
955 B
Text
47 lines
955 B
Text
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]]
|
|
say korasaju(g)
|