Java Graph Related ALgs

TopologicalSort.java

import java.util.*;

public class Main {

    static int MAX_N = 10000;
    static int[] inDegree = new int[MAX_N];
    // link是图的邻接表
    static List<Integer>[] link = new ArrayList[MAX_N];
    // n个节点，m个边
    static int n, m;

    static List<Integer> topologicalSort() {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++)
          // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            if (inDegree[i] == 0)
                queue.add(i);
      
        // 开始执行 BFS 循环
        while (!queue.isEmpty()) {
          // 弹出节点 cur
            int cur = queue.poll();
            res.add(cur);
            cur = -1;
            for (int next:link[cur]) {
              // 并将cur指向的节点的入度减一
               inDegree[next]--;
              // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                if (inDegree[next] == 0)
                    queue.add(next);
            }
        }
        
        // 若排序后节点小于 n，说明存在环
        // 因为BFS算法终止时存在节点没有遍历，环中的节点一定入度都不为零
        return res.size() == n ? res : null;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++)
            link[i] = new ArrayList<>();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            link[x].add(y);
            inDegree[y]++;
        }
        
        List<Integer> ans = topologicalSort();
        if (ans == null)
            System.out.println(-1);
        else 
            ans.forEach(System.out::println);
    }
}