拓扑排序

模版

//初始化图的邻接表及入度
//1到n共n个点，0弃用
in := make([]int, n + 1)
edges := make([][]int, n + 1)
for i := range edges{
    edges[i] = make([]int, 0)
}

//x,y表示x到y的一条边，构建邻接表及入度
for i := 0; i < m; i++{
    var x, y int
    fmt.Scanf("%d%d", &x, &y)
    edges[x] = append(edges[x], y)
    in[y]++
 }
 
 //拓扑排序
 //1.将入度为0的点加入队列
 q := []int{}
 for i := 1; i <= n; i++{
     if in[i] == 0{
        q = append(q, i)
     }
 }
 
 //2.出队并且修改其余顶点的入度
 for len(q) > 0{
     start := q[0]
     q = q[1 : ]
     for _, v := range edges[start]{
         in[v]--
         if in[v] == 0{
            q = append(q, v)
         }
     }
 }

习题

acwing848
LeetCode 207
抖音