Tarjan: Difference between revisions
Go solution
m (→{{header|zkl}}: tweak) |
(Go solution) |
||
Line 82:
}
}</lang>
=={{header|Go}}==
<lang go>package main
import (
"fmt"
"math/big"
)
// (same data as zkl example)
var g = [][]int{
0: {1},
2: {0},
5: {2, 6},
6: {5},
1: {2},
3: {1, 2, 4},
4: {5, 3},
7: {4, 7, 6},
}
func main() {
tarjan(g, func(c []int) { fmt.Println(c) })
}
// the function calls the emit argument for each component identified.
// each component is a list of nodes.
func tarjan(g [][]int, emit func([]int)) {
var indexed, stacked big.Int
index := make([]int, len(g))
lowlink := make([]int, len(g))
x := 0
var S []int
var sc func(int) bool
sc = func(n int) bool {
index[n] = x
indexed.SetBit(&indexed, n, 1)
lowlink[n] = x
x++
S = append(S, n)
stacked.SetBit(&stacked, n, 1)
for _, nb := range g[n] {
if indexed.Bit(nb) == 0 {
if !sc(nb) {
return false
}
if lowlink[nb] < lowlink[n] {
lowlink[n] = lowlink[nb]
}
} else if stacked.Bit(nb) == 1 {
if index[nb] < lowlink[n] {
lowlink[n] = index[nb]
}
}
}
if lowlink[n] == index[n] {
var c []int
for {
last := len(S) - 1
w := S[last]
S = S[:last]
stacked.SetBit(&stacked, w, 0)
c = append(c, w)
if w == n {
emit(c)
break
}
}
}
return true
}
for n := range g {
if indexed.Bit(n) == 0 && !sc(n) {
return
}
}
}</lang>
{{out}}
<pre>
[2 1 0]
[6 5]
[4 3]
[7]
</pre>
=={{header|zkl}}==
| |||