Untitled
unknown
javascript
2 years ago
1.5 kB
4
Indexable
/** * @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 }
Editor is loading...