[Leetcode]207. 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?

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.

Solution

It’s a typical topological sorting problem.

Use a NxN matrix (N is the number of course) to represent the courses graph relationship. Use an array list to store the in-degree of every course. Use a queue to store the nodes which in-degree is 0.

Firstly, go through the input array to construct the graph matrix and record the in-degree of every node at the same time. Then go through the in-degree list, put the nodes which in-degree is 0 into the queue. 

Kahn’s algorithm

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Implementa

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];// int[i][j]==1 means i->j can't be i<-j
        int[] indegree = new int[numCourses];
        
        for(int i = 0; i < prerequisites.length; i++){
            int current = prerequisites[i][0];
            int pre = prerequisites[i][1];
            if( matrix[pre][current] == 0 ){
                indegree[current]++;
            }
             matrix[pre][current] = 1;
        }
        
        Queue<Integer> queue = new LinkedList(); //store 0 indegree nodes
        for(int i = 0 ; i < numCourses; i++){
            if( indegree[i] == 0 ){
                queue.offer(i);
            }
        }
        int count = 0;
        while( !queue.isEmpty() ){
            int current = queue.poll();
            count++;
            for(int i = 0; i < numCourses; i++ ){
                if( matrix[current][i] != 0 ){
                    if (--indegree[i] == 0){
                        queue.offer(i);
                    }
                }
            }
        }
        
        return numCourses == count;
        
        
    }
}

Points

• Horizontal vs Vertical visiting 2D array.