LeetCode 210. Course Schedule II

Problem

207. Course Schedule

1. 题目简述

一共有n门课程需要修，分别是从0到n-1。有些课程需要进行先修课程，我们以数组的形式给出，例如：[0, 1]，就是说如果要修课，必须要上过1课。

现在给出numCourses门课程，和一个prerequisites数组，求给出一种拓扑排序的方式。

2. 算法思路

参考解法：花花酱LeetCode

和LeetCode 207. Course Schedule类似，基本一致，这里不再赘述，直接上解析。

BFS

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // BFS
        int[] inDegree = new int[numCourses];
        Stack<Integer> zeroDegreeVertex = new Stack();
        int res[] = new int[numCourses];
        ArrayList<Integer>[] relations = new ArrayList[numCourses];

        for (int i = 0; i < numCourses; i++) {
            relations[i] = new ArrayList();
        }

        for (int[] prerequisite : prerequisites) {
            inDegree[prerequisite[0]]++;
            relations[prerequisite[1]].add(prerequisite[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                zeroDegreeVertex.push(i);
            }
        }

        int index = 0;
        while (!zeroDegreeVertex.isEmpty() && index != numCourses) {
            res[index] = zeroDegreeVertex.pop();
            for (int vertex : relations[res[index]]) {
                inDegree[vertex]--;
                if (inDegree[vertex] == 0) {
                    zeroDegreeVertex.push(vertex);
                }
            }
            index++;
        }

        if (index != numCourses) {
            return new int[0];
        }

        return res;
    }
}

DFS + backtracking

DFS优化