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") }