Course Schedule

Problem

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?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

Solution

Topological

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int[] indegrees = new int[numCourses];        
        for (int[] p: prerequisites) indegrees[p[0]]++;
        Queue<Integer> q = new LinkedList<>();
        for (int course = 0; course < numCourses; course++) {
            if (indegrees[course] == 0) q.offer(course); 
        }
        int index = 0;
        while (!q.isEmpty()) {
            int course = q.poll();
            index++;
            for (int[] p : prerequisites) { 
                if (p[1] == course) {
                    indegrees[p[0]]--;
                    if (indegrees[p[0]] == 0) q.offer(p[0]);
                }
            }
        }
        return index == numCourses;   
    }  
}

Analysis

Topological solution, please refer to Course Schedule II