我們可以通過(guò)輸入的課程信息構(gòu)成一個(gè)有向圖直晨。比如，示例1中膨俐，輸入2, [[1,0]]勇皇，表明有向圖中有兩個(gè)結(jié)點(diǎn)（0和1），有向圖中有一條环俅獭（0 -> 1）敛摘。因此，我們可以使用鄰接矩陣或者鄰接表構(gòu)造一個(gè)有向圖乳愉。

能完成所有課程兄淫，也就是課程完成的前提條件中沒(méi)有循環(huán)的關(guān)系。比如完成課程A需要先完成課程B蔓姚，完成課程B需要先完成課程A捕虽，這樣就形成了一個(gè)循環(huán)，由結(jié)點(diǎn)A坡脐、B和他們之前的關(guān)系構(gòu)成的有向圖中就存在環(huán)泄私。

因此，如果課程能夠全部完成备闲，課程構(gòu)成的有向圖中就一定沒(méi)有環(huán)晌端。

如何判斷有向圖中有沒(méi)有環(huán)呢？可以用兩種辦法恬砂，一個(gè)是深度優(yōu)先搜索咧纠，通過(guò)深度優(yōu)先搜索來(lái)查找是否有環(huán)存在；一個(gè)是拓?fù)渑判蛐褐瑁邢驁D圖的拓?fù)渑判蛐蛄械某潭鹊扔诮Y(jié)點(diǎn)總數(shù)時(shí)漆羔，有向圖中就不存在環(huán)（反之就存在環(huán)）。

拓?fù)渑判蚴褂绵徑颖肀容^方便狱掂。先構(gòu)造有向圖的鄰接表演痒，然后進(jìn)行拓?fù)渑判颍詈笈袛嗤負(fù)湫蛄虚L(zhǎng)度是不是等于結(jié)點(diǎn)總數(shù)符欠。

深度優(yōu)先搜索用鄰接矩陣表示圖比較方便嫡霞，因此我們先構(gòu)造圖的鄰接矩陣瓶埋，然后使用遞歸進(jìn)行深度優(yōu)先搜索希柿，使用HashSet來(lái)判斷路徑中是否環(huán)的存在诊沪。

三、代碼

3.1 拓?fù)渑判?/h4>

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /**
         * 構(gòu)建鄰接表
        */
        EdgeNode[] edges = new EdgeNode[numCourses]; 
        Node temp = null;
        int topoSize = 0;
        for(int i=0;i<numCourses;i++){
            edges[i] = new EdgeNode();
            edges[i].in = 0;
            edges[i].val = i;
        }
        for(int i=0;i<prerequisites.length;i++){
            temp = edges[prerequisites[i][1]].next;
            Node newNode = new Node();
            newNode.val = prerequisites[i][0];
            edges[prerequisites[i][1]].next = newNode;
            newNode.next = temp;
            edges[prerequisites[i][0]].in ++;
        }
        /**
         * 進(jìn)行拓?fù)渑判?        */
        Stack<EdgeNode> stack = new Stack<EdgeNode>();//存儲(chǔ)入度為0的結(jié)點(diǎn)
        for(int i=0;i<numCourses;i++){                //將入度為0的結(jié)點(diǎn)壓入棧中
            if(edges[i].in==0){
                stack.push(edges[i]);
            }
        }
        EdgeNode deletedNode = null;
        while(!stack.isEmpty()){                      
            topoSize++;
            deletedNode = stack.pop();               //刪除入讀為0的結(jié)點(diǎn)
            temp = deletedNode.next;
            while(temp!=null){                       //更新其鄰接點(diǎn)的入度
                if(edges[temp.val].in>0){
                    edges[temp.val].in --;
                    if(edges[temp.val].in == 0)      //如果更新后的鄰接結(jié)點(diǎn)的入度為0曾撤，將其壓入棧中
                        stack.push(edges[temp.val]);
                }
                temp = temp.next;
            }
        }
        return topoSize == numCourses;
    }
    
    class EdgeNode{                     //鄰接表的邊結(jié)點(diǎn)
        int in;
        int val;
        Node next;
    }
    
    class Node{                            //鄰接結(jié)點(diǎn)
        int val;
        Node next;
    }

3.2 深度優(yōu)先搜索

    HashSet<Integer> set = new HashSet<Integer>();
    boolean[][] adjMat;
    boolean[] visited;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        adjMat = new boolean[numCourses][numCourses];
        visited = new boolean[numCourses];
         /**
          * 構(gòu)建鄰接矩陣
         */
        for(int i=0;i<prerequisites.length;i++){
            adjMat[prerequisites[i][1]][prerequisites[i][0]] = true;
        }
        /**
          * 深度優(yōu)先搜索
         */
        for(int i=0;i<numCourses;i++){
            if(!visited[i]){
                set.clear();
                if(!DFS(i))
                    return false;
            }
        }
        return true;
    }
    
    private boolean DFS(int index){
        visited[index] = true;
        set.add(index);
        for(int i=0;i<visited.length;i++){
            if(adjMat[index][i]&&set.contains(i))
                return false;
            if(!visited[i]&&adjMat[index][i]){
                if(!DFS(i))
                    return false;
            }
        }
        set.remove(index);
        return true;
    }