76 lines
1.7 KiB
Go
76 lines
1.7 KiB
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
|
|
}
|
|
}
|
|
}
|