Tarjan: Difference between revisions
Content added Content deleted
m (→{{header|zkl}}: tweak) |
(Go solution) |
||
Line 82: | Line 82: | ||
} |
} |
||
}</lang> |
}</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}}== |
=={{header|zkl}}== |