给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入格式

第一行包含两个整数n和m

接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。

输出格式

共一行，如果存在拓扑序列，则输出拓扑序列。

否则输出-1。

数据范围

1≤n,m≤105

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

Go 代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

const N = 100010

var n, m int        // n 个点,m 条边的有向图
var h, e, ne [N]int // 邻接表的定义
var idx int
var q, d [N]int // q表示队列, d 表示入度

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
//  new(file)
    new(os.Stdin)

    tmp := readLine()
    n, m = tmp[0], tmp[1] // n 个点,m 条边
    for i := 0; i < N; i++ {
        h[i] = -1 // 链表初始化，头节点指向 -1
    }

    for i := 0; i < m; i++ { // 读入所有边
        x := readLine()
        add(x[0], x[1]) // 插入每条边，有向图
        d[x[1]] ++
    }
    topsort()
}

// 插入一条 a 指向 b 的边
func add(a, b int) {
    // a 所在的邻接表中插入节点 b
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}
func topsort() {
    hh, tt := 0, -1           // 队头队尾
    for i := 1; i <= n; i++ { // 从前往后遍历所有的点
        if d[i] == 0 { // 所有入度为0的点插入到队列里面去
            tt++
            q[tt] = i
        }
    }
    for hh <= tt { // 队列不为空
        t := q[hh] // 取出队头元素
        hh++
        for i := h[t]; i != -1; i = ne[i] { // 扩展队头元素
            j := e[i]      // 找到出边
            d[j] --        // 入度减一
            if d[j] == 0 { // 如果入度为 0
                tt++
                q[tt] = j // 加入到队列
            }
        }
    }
    if tt == n-1 { // tt 等于 n-1,表示队列一共进了 n-1 个点，所有点进入队列，它就是一个有向无环图
        for i := 0; i <= tt; i++ { // 队列里的顺序就是拓扑序
            fmt.Printf("%d ", q[i])
        }
    } else {
        fmt.Println(-1) // 否则所有它是一个存在环的图，不存在拓扑序
    }
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}
func readLine() []int {
    scanner.Scan()
    line := strings.Split(scanner.Text(), " ")
    res := make([]int, len(line))
    for i, l := range line {
        res[i], _ = strconv.Atoi(l)
    }
    return res
}