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

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @BelongsProject: homework
 * @Author: Ling xi_Li
 * @CreateTime: 2023-11-07 10-20
 * @Description: TODO 拓扑排序 卡恩算法
 */

public class Main {
    public static void main(String[] args) throws IOException {

	    //AC的关键，得加速输入输出，因为这个卡了好久。。。。。。
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] firstLine = in.readLine().split(" ");
        //输入点数
        int vNums = Integer.parseInt(firstLine[0]);
        //输入边数
        int eNums = Integer.parseInt(firstLine[1]);

        //用顺序表里面嵌套顺序表来代替图结构
        //嵌套的列表就相当于点，里面存储了它可达的下一个点
        ArrayList<ArrayList<Integer>> Graph = new ArrayList<>(vNums);

        //初始化点
        for (int i = 0; i < vNums; i++) {
            Graph.add(new ArrayList<>());
        }


        //输入边and//点的入度初始化
        int vb = 0;
        int ve = 0;
        int[] Infiltration = new
        int[vNums];//数组大小和点数量一致，一个点对应一个入度
        for (int i = 0; i < eNums; i++) {
            String[] edges = in.readLine().split(" ");
            //起始点
            vb = Integer.parseInt(edges[0]);
            //被指向点
            ve = Integer.parseInt(edges[1]);
            //因为列表索引0开始，点的数值1开始，通过vb-1来获取对应的点
            Graph.get(vb - 1).add(ve - 1);
            //对应的第i个ve点的入度+1
            Infiltration[ve - 1]++;
        }

        in.close();

        //初始化队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vNums; i++) {
            //如果点的入度为0则入队
            if (Infiltration[i] == 0) {
                queue.add(i);
            }
        }


        //存储结果的列表
        ArrayList<Integer> result = new ArrayList<>();

        //统计点的个数看看存不存在环
        int countV = 0;
        //卡恩算法
        while (!queue.isEmpty()) {
            //出队元素加入结果列表同时点个数加一
            int cur = queue.poll();
            result.add(cur);
            countV++;
            //依次遍历出队点（入度为0的点）点对应的下一个点然后将其下一个点的入度-1
            for (int index : Graph.get(cur)) {
                if (--Infiltration[index] == 0) {
                    queue.add(index);
                }
            }
        }

        if (countV == vNums) {
            //出队
            for (int i = 0; i < result.size() - 1; i++) {
                //输出res+1是因为在
                // 初始化图列表时候应下标需要对应的点值都-1了
                // 然后包括添加到queue等一系列操作
                // 都是在操作对应下标现在需要打印了所以+1还原
                out.write(result.get(i) + 1 + " ");
            }
            //1 2 3 4 5
            // 复制样例过来看输出最后一个后面没有空格
            out.write((result.get(result.size() - 1) + 1) + "\n");
        } else {
            //最后一个输出没有空格
            String str = "-1";
            out.write(str);
        }
        out.close();
    }
}