题解 | #【模板】拓扑排序#

let n = Number(arr[0]), m = Number(arr[1]);
const G = new Array(n+1);
for(let i=0; i<=n; i++) {
    G[i] = {val: i, next: null};
}
// 计算每个结点的入度
const indegree = new Array(n+1).fill(0);
while(m--) {
    const line = readline().split(' ');
    const u = Number(line[0]);  // 起始
    const v = Number(line[1]);  // 结束
    // 有向图
    const newArcNode = {
        val: v, next: null
    }
    const next = G[u].next;
    G[u].next = newArcNode;
    newArcNode.next = next;
    // 计算入度
    indegree[v] ++;
}
const stack = [];  // 暂存所有入度为0的顶点
for (let i=1; i<=n; i++) {
    if (indegree[i] === 0)
        // 入度为0的顶点入栈
        stack.push(i); 
}
const topo = [];  // 记录拓扑序列的顶点序号
while(stack.length > 0) {
    // 出栈，并存入拓扑序列中
    const i = stack.pop()
    topo.push(i);
    // 将顶点P的所有邻接点的入度减1
    let p = G[i].next;
    while(p != null) {
        const k = p.val;
        indegree[k] --;
        if (indegree[k]===0){
            stack.push(k);
        }
        p = p.next;
    }
}
if(topo.length < n) 
    print(-1);
else
    print(topo.join(' '));