题解 | 【模板】拓扑排序

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int n,m;
    public static int max=200001;
    public static int[]indegree=new int[max];
    public static int[]ans=new int[max];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
         n=in.nextInt();
         m=in.nextInt();
        ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }
        Arrays.fill(indegree,0,n+1,0);
        for(int i=0,from,to;i<m;i++){
          from=in.nextInt();
          to=in.nextInt();
          graph.get(from).add(to);
          indegree[to]++;
        }
        if(!topoSort(graph)){
            System.out.println(-1);
        }else{
            for(int i=0;i<n-1;i++){
                System.out.print(ans[i]+" ");
            }
            System.out.println(ans[n-1]);
        }
    }
    public static int[]queue=new int[max];
    public static int r,l;
    public static boolean topoSort(ArrayList<ArrayList<Integer>>graph){
        l=r=0;
        for(int i=1;i<=n;i++){
             if(indegree[i]==0){
                queue[r++]=i;
             }
        }
        int fill=0;
        while(l<r){
            int cur=queue[l++];
            ans[fill++]=cur;
            for(int next:graph.get(cur)){
                if(--indegree[next]==0){
                    queue[r++]=next;
                }
            }
        }
        return fill==n;
    }
}