题解 | 【模板】拓扑排序

import java.util.*;

import java.lang.String; 

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int edges = scanner.nextInt();
        scanner.nextLine();

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }

        int[] indegree = new int[n];
        for (int i = 0; i < edges; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            scanner.nextLine();
            graph.get(u).add(v);
            indegree[v]++;
        }

        boolean flag = sort(graph, indegree, n);
        if (flag) {
            StringBuilder sb = new StringBuilder();
            for (Integer i : list) {
                sb.append(i);
                sb.append(" ");
            }
            sb.deleteCharAt(sb.length()-1);
            System.out.println(sb.toString());
        } else {
            System.out.println("-1");
        }
        
    }


    private static boolean sort(Map<Integer, List<Integer>> graph,
                                      int[] indegree, int n) {
        int cnt = 0;                               
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.add(i); // 加入chu shi jie dian
            }
        }
        while (!queue.isEmpty()) {
            int u = queue.poll();
            list.add(u + 1);
            List<Integer> neighbors = graph.get(u);
            for (Integer neighbor : neighbors) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
            graph.get(u).clear();
            cnt++;
        }
        return cnt == indegree.length;
    }

}