blob: 7518080c63a56b9ff37355f3d65468a1d9604416 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
package hbt
import collection.mutable
// Adapted from
// https://github.com/indy256/codelibrary/blob/c52247216258e84aac442a23273b7d8306ef757b/java/src/SCCTarjan.java
object Tarjans {
def apply(graph0: Seq[Seq[Int]]): Seq[Seq[Int]] = {
val graph = graph0.map(_.toArray).toArray
val n = graph.length
val visited = new Array[Boolean](n)
val stack = mutable.ArrayBuffer.empty[Integer]
var time = 0
val lowlink = new Array[Int](n)
val components = mutable.ArrayBuffer.empty[Seq[Int]]
for (u <- 0 until n) {
if (!visited(u)) dfs(u)
}
def dfs(u: Int): Unit = {
lowlink(u) = time
time += 1
visited(u) = true
stack.append(u)
var isComponentRoot = true
for (v <- graph(u)) {
if (!visited(v)) dfs(v)
if (lowlink(u) > lowlink(v)) {
lowlink(u) = lowlink(v)
isComponentRoot = false
}
}
if (isComponentRoot) {
val component = mutable.Buffer.empty[Int]
var done = false
while (!done) {
val x = stack.last
stack.remove(stack.length - 1)
component.append(x)
lowlink(x) = Integer.MAX_VALUE
if (x == u) done = true
}
components.append(component)
}
}
components
}
}
|