Tarjan: Difference between revisions
Content deleted Content added
Go solution |
Added Kotlin |
||
Line 164: | Line 164: | ||
[6 5] |
[6 5] |
||
[4 3] |
[4 3] |
||
[7] |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
<lang scala>// version 1.1.3 |
|||
import java.util.Stack |
|||
typealias Nodes = List<Node> |
|||
class Node(val n: Int) { |
|||
var index = -1 // -1 signifies undefined |
|||
var lowLink = -1 |
|||
var onStack = false |
|||
override fun toString() = n.toString() |
|||
} |
|||
class DirectedGraph(val vs: Nodes, val es: Map<Node, Nodes>) |
|||
fun tarjan(g: DirectedGraph): List<Nodes> { |
|||
val sccs = mutableListOf<Nodes>() |
|||
var index = 0 |
|||
val s = Stack<Node>() |
|||
fun strongConnect(v: Node) { |
|||
// Set the depth index for v to the smallest unused index |
|||
v.index = index |
|||
v.lowLink = index |
|||
index++ |
|||
s.push(v) |
|||
v.onStack = true |
|||
// consider successors of v |
|||
for (w in g.es[v]!!) { |
|||
if (w.index < 0) { |
|||
// Successor w has not yet been visited; recurse on it |
|||
strongConnect(w) |
|||
v.lowLink = minOf(v.lowLink, w.lowLink) |
|||
} |
|||
else if (w.onStack) { |
|||
// Successor w is in stack s and hence in the current SCC |
|||
v.lowLink = minOf(v.lowLink, w.index) |
|||
} |
|||
} |
|||
// If v is a root node, pop the stack and generate an SCC |
|||
if (v.lowLink == v.index) { |
|||
val scc = mutableListOf<Node>() |
|||
do { |
|||
val w = s.pop() |
|||
w.onStack = false |
|||
scc.add(w) |
|||
} |
|||
while (w != v) |
|||
sccs.add(scc) |
|||
} |
|||
} |
|||
for (v in g.vs) if (v.index < 0) strongConnect(v) |
|||
return sccs |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val vs = (0..7).map { Node(it) } |
|||
val es = mapOf( |
|||
vs[0] to listOf(vs[1]), |
|||
vs[2] to listOf(vs[0]), |
|||
vs[5] to listOf(vs[2], vs[6]), |
|||
vs[6] to listOf(vs[5]), |
|||
vs[1] to listOf(vs[2]), |
|||
vs[3] to listOf(vs[1], vs[2], vs[4]), |
|||
vs[4] to listOf(vs[5], vs[3]), |
|||
vs[7] to listOf(vs[4], vs[7], vs[6]) |
|||
) |
|||
val g = DirectedGraph(vs, es) |
|||
val sccs = tarjan(g) |
|||
println(sccs.joinToString("\n")) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
[2, 1, 0] |
|||
[6, 5] |
|||
[4, 3] |
|||
[7] |
[7] |
||
</pre> |
</pre> |