基础
拓扑排序用于给有向图(允许存在重边和自环)排序。在写法上非常接近基于邻接表的BFS(就是多加了入度出度的计算)
- 入度:某点接受来自别处的一条边,该点的入度加一
- 换句话说,当指向该点的边消失,该点的入度就会减一
- 进入拓扑排序候选队列的条件(类似bfs):该点的入度 == 0
package main
import (
"fmt"
"os"
"bufio"
"strings"
"strconv"
)
const N = 100010
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
readLine = func() []int {
in.Scan()
l := strings.Split(in.Text(), " ")
res := make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return res
}
idx int
e, h, ne [N]int
din, q [N]int
n, m int
)
func add(a, b int) {
e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx++
}
func topSort() bool {
hh, tt := 0, -1
for i := 1; i <= n; i++ {
if din[i] == 0 {tt++; q[tt] = i}
}
for hh <= tt {
t := q[hh]; hh++
for i := h[t]; i != -1; i = ne[i] {
j := e[i]; din[j]--
if din[j] == 0 {tt++; q[tt] = j}
}
}
return tt == n - 1
}
func main() {
defer out.Flush()
h[0] = -1; for i := 1; i < N; i *= 2{copy(h[i:], h[:i])}
cur := readLine()
n, m = cur[0], cur[1]
for; m > 0; m-- {
tmp := readLine()
a, b := tmp[0], tmp[1]
din[b]++
add(a, b)
}
if !topSort() {
fmt.Fprintln(out, -1)
} else {
for i := 0; i < n; i++ {fmt.Fprint(out, q[i], " ")}
}
}
进阶:建图优化
拓扑排序里涉及建图,而当遇到这样的情况,有一招优化,能把时间复杂度从O(n ^ 2)降到O(n + m)
就步骤来说,也是建一个虚拟点