Problem

This is also like before problem. Here we have to find all valid sequences out of given number of courses and prerequesites. 

Example

Given number of courses :: 2
Prerequesites :: [[0,1]]
Output :: [0,1]

Given number of courses :: 2
Prerequesites :: [[0,1][1,0]]
Output :: []

JavaScript Code

function findOrder(numCourses,  prerequisites) {
    if(prerequisites == null){
        return;
    }
 
    var len = prerequisites.length;
 
    //if there is no prerequisites, return a sequence of courses
    if(len == 0){
        var res = [];
        for(var m=0; m<numCourses; m++){
            res[m]=m;
        }
        return res;
    }
 
    //records the number of prerequisites each course (0,...,numCourses-1) requires
    var  pCounter = [];
    //initialize result
    var  result = [];
    for(var m=0; m<numCourses; m++){
        pCounter[m]=0;
        result[m]=0;
    }
    for(var i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //stores courses that have no prerequisites
    var queue = [];
    for(var i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.push(i);
        }
    }
 
    var numNoPre = queue.length;
 
    var j=0;
 
    while(queue.length!=0){
        var c = queue.shift();
        result[j++]=c;
 
        for(var i=0; i<len; i++){
            if(prerequisites[i][1]==c){
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    queue.push(prerequisites[i][0]);
                    numNoPre++;
                }
            }
 
        }
    }
 
    //return result
    if(numNoPre==numCourses){
        return result;
    }else{
        return [];
    }
}

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

0 comments:

Blogroll

Follow this blog by Email

Popular Posts