問題描述：

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

在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們: [0,1]

給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學習？

示例 1:

輸入:2, [[1,0]]輸出: true解釋:總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。

示例 2:

輸入:2, [[1,0],[0,1]]輸出: false解釋:總共有 2 門課程。學習課程 1 之前，你需要先完成?課程 0；并且學習課程 0 之前，你還應先完成課程 1。這是不可能的。

說明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請參見圖的表示法。

你可以假定輸入的先決條件中沒有重復的邊。

提示:

這個問題相當于查找一個循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓撲排序，因此不可能選取所有課程進行學習。

DFS深度優(yōu)先探索是算法筆試、面試中經常遇到的問題，我覺得這道題是一個很好得例子，下面為代碼

優(yōu)化前：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<ArrayList<Integer>> grah = new ArrayList<>();
        for(int i=0;i<numCourses;i++)
            grah.add(new ArrayList<>());
        
        for(int i=0;i<prerequisites.length;i++){
            grah.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        
        int[] visited = new int[numCourses];
        
        for(int i=0;i<numCourses;i++){
            //判斷是否有環(huán)
            if(dfs(grah,visited,i))
                return false;
        }
        
        //發(fā)現(xiàn)無環(huán)，則返回true
        return true;
    }
    
    public boolean dfs(List<ArrayList<Integer>> grah,int[] visited,int num){
        //如果已經被訪問過，則發(fā)現(xiàn)環(huán)
        if(visited[num] == 1)
            return true;

        
        visited[num] = 1;//表示已經訪問過此節(jié)點
        for(int id : grah.get(num)){
            if(dfs(grah,visited,id))
                return true;
        }
        visited[num] = 0;//去掉訪問此節(jié)點標記
        
        return false;        
    }
}

測試結果：

1546595234(1).png

優(yōu)化：
其實優(yōu)化方式很簡單，原來的標記為：0-未訪問過；1-訪問過
在此基礎上多加一個標記：0-未訪問過；1-訪問過；2-曾經訪問過但是當前沒訪問
多加這個標記可以理解為，如果曾經訪問過這個節(jié)點時不存在環(huán)，那么從這節(jié)點走下去也不會存在環(huán)，直接返回false就可以了。下面為代碼，改動只有一點點哦

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<ArrayList<Integer>> grah = new ArrayList<>();
        for(int i=0;i<numCourses;i++)
            grah.add(new ArrayList<>());
        
        for(int i=0;i<prerequisites.length;i++){
            grah.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        
        int[] visited = new int[numCourses];
        
        for(int i=0;i<numCourses;i++){
            //判斷是否有環(huán)
            if(dfs(grah,visited,i))
                return false;
        }
        
        //發(fā)現(xiàn)無環(huán)，則返回true
        return true;
    }
    
    public boolean dfs(List<ArrayList<Integer>> grah,int[] visited,int num){
        //如果已經被訪問過，則發(fā)現(xiàn)環(huán)
        if(visited[num] == 1)
            return true;
        //曾經訪問過，但從此節(jié)點走下去不存在環(huán)
        if(visited[num] == 2)
            return false;
        
        visited[num] = 1;//添加訪問標記
        for(int id : grah.get(num)){

            if(dfs(grah,visited,id))
                return true;
        }
        visited[num] = 2;//去掉被訪問標記
        
        return false;        
    }
}

運行結果

1546595248(1).png

優(yōu)化結果是不是非常明顯，哈哈

之后會更新BFS的解法~