123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 |
- #!/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])
|