题目描述

拓扑排序

思想

基于宽度搜索，存储节点的边信息，head[0]=[1,3]
在此有种方案，A.存后置节点:0->1,0->3,B.存前置节点:1->0,3->0
B方案方便计算入度值，A则需for循环
但是在删除某个节点后，A方案方便计算入度变化值，B则需要for循环，时间复杂度高O(n),
入度初始值计算一次，变化值多次，故选择A方案

go 代码

package main
import "fmt"

func main(){
    var node_num, edge_num int
    fmt.Scanf("%d %d",&node_num,&edge_num)
    head :=make([][]int,node_num)
    in_degree :=make([]int,node_num)

    for edge_num>0{
        var start,end int
        fmt.Scanf("%d %d",&start,&end)
        // 指向的节点，不是被指向的节点
        head[start-1] = append(head[start-1],end)
        in_degree[end-1]++
        edge_num--
    }

    q :=make([]int,0)
    for idx,val:=range in_degree{
        if val == 0{
            q =append(q,idx+1)
        }
    }
    path:=make([]int,len(q))
    copy(path,q)

    for len(q) >0 {
        start :=q[0]
        q =q[1:]
        // 将以start头的边删除，并检查点的入度是否为零
        for _,val:= range head[start-1]{
            in_degree[val-1]--
            if in_degree[val-1] ==0{
                q =append(q,val)
                path =append(path,val)
            }
        }
    }
    if len(path) == node_num{
        for _,val:=range path{
            fmt.Printf("%d ",val)
        }
    }else{
        fmt.Println(-1)
    }
}