描述

現(xiàn)在你總共有 n 門課需要選，記為 0 到 n - 1.
一些課程在修之前需要先修另外的一些課程，比如要學(xué)習(xí)課程 0 你需要先學(xué)習(xí)課程 1 ，表示為[0,1]
給定n門課以及他們的先決條件，判斷是否可能完成所有課程？

樣例

給定 n = 2，先決條件為 [[1,0]] 返回 true
給定 n = 2，先決條件為 [[1,0],[0,1]] 返回 false

代碼

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // edges用來存儲每一門課程對應(yīng)的所有后續(xù)課程
        // 此處新建edges的寫法要注意
        List[] edges = new ArrayList[numCourses];
        int[] degree = new int[numCourses];
        
        // edges[i]本身就是一個動態(tài)數(shù)組，初始化edges
        for (int i = 0;i < numCourses; i++)
            edges[i] = new ArrayList<Integer>();
            
        for (int i = 0; i < prerequisites.length; i++) {
            // 題目給出的prerequisites[i][1]是先修課程，prerequisites[i][0]是后續(xù)課程
            // 統(tǒng)計學(xué)習(xí)某門課需要先修的課程數(shù)目,即入度
            degree[prerequisites[i][0]]++ ;
            // 即把某門課的后續(xù)課程全部加入到該課對應(yīng)的edges數(shù)組中
            edges[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        
        // degree數(shù)組中i代表的的是某一門課程
        // 把度為0的課程加入隊列
        Queue queue = new LinkedList();
        for(int i = 0; i < degree.length; i++){
            if (degree[i] == 0) {
                queue.add(i);
            }
        }
        
        int count = 0;
        while(!queue.isEmpty()){
            // 隊列里存儲的是Integer
            int course = (int)queue.poll();
            count ++;
            // n代表當(dāng)前課程的后續(xù)課程的數(shù)目
            int n = edges[course].size();
            // 每處理一門課程，該課程的后續(xù)課程的度都要-1
            for(int i = 0; i < n; i++){
                int pointer = (int)edges[course].get(i);
                degree[pointer]--;
                if (degree[pointer] == 0) {
                    queue.add(pointer);
                }
            }
        }
        
        // 處理的課程數(shù)目等于所有課程說明所有課程之間可以構(gòu)成拓撲排序
        return count == numCourses;
    }
}