拓扑排序

• OI Wiki: https://oi-wiki.org/graph/topo/

题目	难度
207. 课程表	中等
210. 课程表 II	中等
630. 课程表 III	困难	贪心
1462. 课程表 IV	中等	Floyd 最短路
$1136. 并行课程	中等
1494. 并行课程 II	困难	状态压缩 动态规划
2050. 并行课程 III	困难	拓扑排序 动态规划

Kahn 算法

210. 课程表 II

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 拓扑排序
        Map<Integer, List<Integer>> outGraph = new HashMap<>();
        int[] inDegrees = new int[numCourses];

        // 其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
        for (int[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];
            outGraph.computeIfAbsent(from, key -> new ArrayList<>()).add(to);
            inDegrees[to]++;
        }

        // 入度为 0 进队列。记为 0 到 numCourses - 1
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) {
                queue.add(i);
            }
        }
        List<Integer> resList = new ArrayList<>();
        while (!queue.isEmpty()) {
            int cur = queue.remove();
            resList.add(cur);

            for (int next : outGraph.getOrDefault(cur, new ArrayList<>())) {
                inDegrees[next]--;
                if (inDegrees[next] == 0) {
                    queue.add(next);
                }
            }
        }
        if (resList.size() == numCourses) {
            return resList.stream().mapToInt(i -> i).toArray();
        }
        return new int[]{};
    }
}

（全文完）