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

import java.util.*;
public class Main{
    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int n = Integer.parseInt(str[0]);
        Graph graph = new Graph(n);
        while(sc.hasNextLine()){
            String[] line = sc.nextLine().split(" ");
            int u = Integer.parseInt(line[0]);//开始顶点、
            int v = Integer.parseInt(line[1]);
            //入度加1
            graph.inDegree[v-1]++;
            //u点增加出度（邻接链表）
            graph.list.get(u-1).add(v-1);    
        }
        if(graph.topologincalSort()){
            for(int num:graph.res){
                System.out.print(num+" ");
            }
        }else
            System.out.println("-1");
    }
}
class Graph{
    public int[] inDegree;
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public List<Integer> res = new ArrayList<>();
    public Graph(int n){
        inDegree = new int[n];
        for(int i=0;i<n;i++)
            list.add(new ArrayList<>());
    }
    public boolean topologincalSort(){
        int num = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i<inDegree.length;i++)
            if(inDegree[i] == 0)
                stack.push(i);
        while(!stack.isEmpty()){
            int u = stack.pop();
            res.add(u+1);
            int len = list.get(u).size();
            for(int i=0;i<len;i++){
                int v = list.get(u).get(i);
                inDegree[v]--;
                if(inDegree[v]==0)
                    stack.push(v);
            }
            list.get(u).clear();
            num++;
        }
        return num == inDegree.length; 
    }
}

总结： 拓扑排序需要借助栈，将入度为0的顶点入栈。