現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1。

在選修某些課程之前需要一些先修課程。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來(lái)表示他們: [0,1]

給定課程總量以及它們的先決條件，返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序。

可能會(huì)有多個(gè)正確的順序，你只要返回一種就可以了。如果不可能完成所有課程，返回一個(gè)空數(shù)組。

https://leetcode-cn.com/problems/course-schedule-ii/

示例1：

輸入: 2, [[1,0]]
輸出: [0,1]
解釋: 總共有 2 門課程。要學(xué)習(xí)課程 1，你需要先完成課程 0。因此，正確的課程順序?yàn)?[0,1] 。

示例2：

輸入: 4, [[1,0],[2,0],[3,1],[3,2]]
輸出: [0,1,2,3] or [0,2,1,3]
解釋: 總共有 4 門課程。要學(xué)習(xí)課程 3，你應(yīng)該先完成課程 1 和課程 2。并且課程 1 和課程 2 都應(yīng)該排在課程 0 之后。
因此，一個(gè)正確的課程順序是 [0,1,2,3] 。另一個(gè)正確的排序是 [0,2,1,3] 。

提示：

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請(qǐng)參見(jiàn)圖的表示法。
你可以假定輸入的先決條件中沒(méi)有重復(fù)的邊。
這個(gè)問(wèn)題相當(dāng)于查找一個(gè)循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓?fù)渑判颍虼瞬豢赡苓x取所有課程進(jìn)行學(xué)習(xí)。
通過(guò) DFS 進(jìn)行拓?fù)渑判?- 一個(gè)關(guān)于Coursera的精彩視頻教程（21分鐘），介紹拓?fù)渑判虻幕靖拍睢?br> 拓?fù)渑判蛞部梢酝ㄟ^(guò) BFS 完成。

Java解法

思路：

• 之前做過(guò)Day82 課程表，這里參考同樣的解法，通過(guò)深度搜索+回溯+狀態(tài)記錄來(lái)完成
  • 狀態(tài)記錄當(dāng)前位置是否被掃描過(guò)，已處理；處理中；未處理
    對(duì)于訪問(wèn) 已是處理中的情況，表明有環(huán)，不能完成學(xué)習(xí)
  • 這里有個(gè)問(wèn)題，上次是判斷能不能遍歷完成，這次要記錄遍歷順序，有點(diǎn)逗比，考慮用hashmap分別記錄不同結(jié)點(diǎn)遍歷結(jié)束的情況， 然而實(shí)際上不用這么操作，參考官方解，遍歷到最后位置的結(jié)點(diǎn)，直接放入結(jié)果數(shù)組的最后結(jié)點(diǎn)即可

class Solution {

     List<List<Integer>> learnRule;
     int[] learnStatus; //0未處理;1處理中;2已處理
     int[] result;
     boolean canLearn = true;
    // 棧下標(biāo)
     int index;
    public  int[] findOrder(int numCourses, int[][] prerequisites) {
        learnRule = new ArrayList<>();
        learnStatus = new int[numCourses];
        result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            learnRule.add(new ArrayList<>());
        }
        index = numCourses - 1;
        for (int[] prerequisite : prerequisites) {
            learnRule.get(prerequisite[1]).add(prerequisite[0]);
        }
        for (int i = 0; i < learnStatus.length && canLearn; i++) {
            if (learnStatus[i] == 0) {
                dfs(i);
            }
        }
        if (!canLearn) {
            return new int[0];
        }
        return result;
    }

    private  void dfs(int i) {
        learnStatus[i] = 1;
        //對(duì)i進(jìn)行深度搜索
        for (Integer integer : learnRule.get(i)) {
            if (learnStatus[integer] == 1) {
                //有環(huán)
                canLearn = false;
                return;
            } else if(learnStatus[integer] == 0) {
                dfs(integer);
                if (!canLearn) {
                    return;
                }
            }
        }
        learnStatus[i] = 2;
        // 將節(jié)點(diǎn)入棧
        result[index--] = i;
    }
}

image

官方解

https://leetcode-cn.com/problems/course-schedule-ii/solution/ke-cheng-biao-ii-by-leetcode-solution/

1. 深度優(yōu)先搜索：參考解，牛逼牛逼，圖結(jié)構(gòu)不太熟悉，但dfs可以好好用用

2. 廣度優(yōu)先搜索：入度操作可以參考一下