leetCode：210. Course Schedule II

leetCode の「210. Course Schedule II」を解いた。
https://leetcode.com/problems/course-schedule-ii/

トポロジカルソートの良い練習問題なので、今後の参考のため自分の解答をここに残しておく。

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }

        // 学習中のコース
        Queue<Integer> readyToStudy = new ArrayDeque<>();

        // 入次数 (このコースを前提とするコース数)
        int[] inDegree = new int[numCourses];

        // Src course -> Dest courses (Src course に依存するコース群)
        Map<Integer, List<Integer>> courseMap = new HashMap<>();

        for (int[] prerequisite : prerequisites) {
            int src = prerequisite[1];
            int dest = prerequisite[0];
            inDegree[dest]++;
            List<Integer> destList = courseMap.getOrDefault(src, new ArrayList<>());
            destList.add(dest);
            courseMap.put(src, destList);
        }

        for (int i = 0; i < inDegree.length; i++) {
            // 入次数 (このコースを前提とするコース数) が 0 のものは受講可能
            if (inDegree[i] == 0) {
                readyToStudy.offer(i);
            }
        }

        // 受講完了したコースを順に格納する。
        int[] finishedCourses = new int[numCourses];
        int finishedCount = 0;
        while (!readyToStudy.isEmpty()) {
            int studied = readyToStudy.poll(); // 受講
            finishedCourses[finishedCount++] = studied;
            List<Integer> destList = courseMap.get(studied);
            if (destList == null) {
                continue;
            }
            for (int dest : destList) {
                // 受講完了したコースを前提としているコースの inDegree を -1 する。
                inDegree[dest]--;
                // 1 を減算後、そのコースの inDegree が 0 になったら受講可能 ⇒ readyToStudy キューに入れる。
                if (inDegree[dest] == 0) {
                    readyToStudy.offer(dest);
                }
            }
        }

        // finishedCount が 全体のコース数と同じだったら、全てのコースを受講したということ。
        if (finishedCount == numCourses) {
            return finishedCourses;
        }
        else {
            return new int[0];
        }
    }
}