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?

Examples

Given 2 and [[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.

Given 2 and [[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.

JavaScript Code

function canFinish(numCourses, prerequisites) {
    if(prerequisites == null){
        return;
    }
 
    var len = prerequisites.length;
 
    if(numCourses == 0 || len == 0){
        return true;
    }
 
    // counter for number of prerequisites
    var pCounter = [];
    for(var i=0; i<numCourses; i++){
        pCounter[i] = 0;
    }
    for(var i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //store courses that have no prerequisites
    var queue = [];
    for(var i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.push(i);
        }
    }
 
    // number of courses that have no prerequisites
    var numNoPre = queue.length;
 
    while(queue.length != 0){
        var top = queue.shift();
        for(var i=0; i<len; i++){
            // if a course's prerequisite can be satisfied by a course in queue
            if(prerequisites[i][1]==top){
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    numNoPre++;
                    queue.push(prerequisites[i][0]);
                }
            }
        }
    }
 
    return numNoPre == numCourses;
}

console.log(canFinish(2, [[1,0],[0,1]]));

0 comments:

Blogroll

Popular Posts