Course Schedule

Question

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Solution

這題的核心概念就在於 topological sort。topological sort 就是在處理類似 pipeline 的概念，這個 task 不會擋到下個 task，或這個 task 做完可以接著做那個 task。對應到這題，就會變成這門課修了之後才可以接著修哪門課。以圖論來討論的話，它會是個有向圖，只要這個有向圖有 cycle，那就代表沒有 topological order 存在，因此也就無法全部課程都修完

特別要注意的是，我第一次寫是用 map，但看了解答發現用 array 就好。但因為數字跟 index 是相同的，因此要搞清楚到底該存進 array 的是 index 或是真正的數字

public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];

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

        for (int i = 0; i < prerequisites.length; i++) {
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
            inDegree[prerequisites[i][1]]++;
        }

        int result = 0;
        Queue<Integer> queue = new LinkedList<Integer>();

        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                result++;
            }
        }

        while (!queue.isEmpty()) {
            int courseIndex = queue.poll();
            for (int i = 0; i < graph[courseIndex].size(); i++) {
                int course = (int)graph[courseIndex].get(i);
                inDegree[course]--;
                if (inDegree[course] == 0) {
                    System.out.println(course);
                    queue.offer(course);
                    result++;
                }
            }
        }

        return result == numCourses;
    }