golang 解拓扑序列

题目描述

给定一个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

golang

package main

import "fmt"

const N = 100010

var e [N]int
var ne [N]int
var h [N]int
var idx int
var invec [N]int

func add(a, b int) {
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}

var n, m int

var queue [N]int

func main() {
    for i := 0; i < N; i++ {
        h[i] = -1
    }

    fmt.Scanf("%d%d", &n, &m)
    for i := 0; i < m; i++ {
        a, b := 0, 0
        fmt.Scanf("%d%d", &a, &b)
        add(a, b)
        invec[b]++
    }

    if !toposort() {
        fmt.Println(-1)
    } else {
        for i := 0; i < n; i++ {
            fmt.Printf("%d ", queue[i])
        }
        fmt.Println("")
    }

}

func toposort() bool {
    hh, tt := 0, -1
    for i := 1; i <= n; i++ {
        if invec[i] == 0 {
            tt++
            queue[tt] = i
        }
    }
    for hh <= tt {
        val := queue[hh]
        hh++
        for i := h[val]; i != -1; i = ne[i] {
            elem := e[i]
            invec[elem]--
            if invec[elem] == 0 {
                tt++
                queue[tt] = elem
            }
        }
    }

    return tt == n-1
}