Untitled

mail@pastecode.io avatar
unknown
javascript
a year ago
1.5 kB
1
Indexable
Never
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
  if(prerequisites[0]==undefined) return true
  let bool = true
    let adjGraph = buildAdj(prerequisites)
        console.log("adj matrix",adjGraph)
    for(let i =0;i<numCourses; i++){
    if(dfs(adjGraph, numCourses, i )==false){
      console.log("got false")
      bool =false
      break
      return bool
    };

    }
    return bool
 
};

let dfs = (adjGraph,numCourses,start)=>{
    let stack = [[start, start]];
    let visit = new Set();
    let store = []
   // visit.add(start)
    while(stack.length >0){
      let [current,parent] = stack.pop();
         if(adjGraph[current]==undefined) continue

      for(sibiling of adjGraph[current]){
        console.log(visit.has(sibiling), parent, sibiling,visit ,visit.has(sibiling))
        if(visit.has(sibiling) && store[sibiling]!== parent ){return false; break} else
        if(!visit.has(sibiling)){
              visit.add(sibiling);
              store[sibiling] = parent
        stack.push([sibiling, current])
        }
      
      }
    }
    return true

    
} 

let buildAdj = (graph)=>{
    let obj ={}
    graph.forEach((nodes)=>{
      //  console.log(nodes);
        let [to , take] = nodes;
        if(!(!!obj[take])) obj[take]=[];
              if(!(!!obj[to])) obj[to]=[];
        obj[take].push(to);
    
    })
    return obj
}