package main import fmt type Rib struct in out int var orgraph int var

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package main
import "fmt"
type Rib struct {
in, out int
}
var orgraph [][]int
var condel [][]int
var condribs [] Rib
type Vertex struct {
time, comp, low int
}
var time, count, stak int
func VVTarjan(vertex []Vertex, num int, stack []int) {
var prom Rib
vertex[num].time, vertex[num].low, time = time, time, time+1
stack[stak] = num
stak++
for i := 0; i < len(vertex); i++ {
if orgraph[num][i] == 1 {
if vertex[i].time == 0 {
VVTarjan(vertex, i, stack)
}
if (vertex[i].comp == 0) && (vertex[num].low > vertex[i].low) {
vertex[num].low = vertex[i].low
}
if vertex[i].comp != 0 {
prom.in, prom.out = i, num
condribs = append(condribs, prom)
}
}
}
j := 0
if vertex[num].time == vertex[num].low {
condel = append(condel, make([]int, 0))
A: stak--
j = stack[stak]
condel[count-1] = append(condel[count-1], j)
vertex[j].comp = count
if j != num { goto A }
count++
}
}
func Tarjan(vertex []Vertex) int {
time, count = 1, 1
stack := make([]int, len(vertex))
for i := 0; i < len(vertex); i++ {
if vertex[i].time == 0 {
VVTarjan(vertex, i, stack)
}
}
res := 0
for i := 0; i < len(vertex); i++ {
if vertex[i].comp > res { res = vertex[i].comp }
}
return res
}
func inside(arr []int) bool {
for i := 0; i < len(arr); i++ {
if arr[i] == -1 { return false }
}
return true
}
func main() {
var n, m int
fmt.Scanf("%d %d", &n, &m)
vertex := make([]Vertex, n)
orgraph = make([][]int, n)
condel = make([][]int, 0)
for i := 0; i < n; i++ {
orgraph[i] = make([]int, n)
}
var node1, node2 int
for i := 0; i < m; i++ {
fmt.Scanf("%d %d", &node1, &node2)
orgraph[node1][node2] = 1
}
Tarjan(vertex)
condrgaph := make([][]int, len(condel))
for i := 0; i < len(condel); i++ {
condrgaph[i] = make([]int, len(condel))
}
for i := 0; i < len(condribs); i++ {
condrgaph[vertex[condribs[i].out].comp-1][vertex[condribs[i].in].comp-1] = 1
condrgaph[vertex[condribs[i].in].comp-1][vertex[condribs[i].out].comp-1] = -1
}
for i := 0; i < len(condel); i++ {
if inside(condrgaph[i]) {
fmt.Printf("%d ", condel[i][len(condel[i])-1])
}
}
fmt.Printf("\n")
}