Explanation on WHY/HOW cycle was detected(The crux of the problem) -As we perform dfs, we add node to 'visited' set if it does not exist. -Once we have exhausted all its neighbors/prerequisites AND return back to it from callstack, we pop it from call stack and we remove from 'visited' set. -A cycle is detected when the node we are popping off of call stack still exists in 'visited' set. Or another way to think is that we popped it from callstack, and yet it still exists somewhere in the callstack already from prior call. Since we cant directly access callstack. ex: @ 1:06 (cycle between 0 and 1) Here we are about to pop 0 from call stack and yet it still exists in call stack at bottom. Since we are not able to directly access callstack , i think this is why we use the 'visited' set. visited { 0, 1} | 1 | //pop from stack, BUT still exists in our visited set and callstack | 0 | | 1 |
-Yea that threw me off a a bit. Instead can replace with : if (!adjList[course] || adjList[course].length == 0) { return true //or simply just 'return' } -Or you can simply omit this conditional check as it isn't really compulsory.
Sorry it doesn't work on submission ,. there is some issue in adjacent list hat is being generated by your code. there might be some duplicate in my code but it works. @AlgoJS can you pin var canFinish = function (numCourses, prerequisites) { let adajencyList = new Map(); let visited = new Set(); function addNode(airport) { adajencyList.set(airport, []); } function addEdge(pre, post) { adajencyList.get(post).push(pre); } let totalNodes = Array.from({ length: numCourses }, (v, i) => parseInt(i)); totalNodes.forEach(addNode); prerequisites.forEach((pre) => addEdge(...pre)); function dfs(curr) { if (visited.has(curr)) return false; let child = adajencyList.get(curr); visited.add(curr); if (child.length !== 0) { if (adajencyList.get(curr).length == 0) return true; for (let index = 0; index < child.length; index++) { if (!dfs(child[index])) return false; } } visited.delete(curr); adajencyList.set(curr, []); return true; } for (let [key, value] of adajencyList) { if (!dfs(key)) { return false; } } return true; };
Wow, this is hard one. Thanks for your content, it helps a lot! The best channel of solving leetcode tasks I've ever seen
Amazing comment, thanks denchke. Keep grinding leetcode!
@@AlgoJS Thanks for your content, it means a world to me
Explanation on WHY/HOW cycle was detected(The crux of the problem)
-As we perform dfs, we add node to 'visited' set if it does not exist.
-Once we have exhausted all its neighbors/prerequisites AND return back to it from callstack, we pop it from call stack
and we remove from 'visited' set.
-A cycle is detected when the node we are popping off of call stack still exists in 'visited' set. Or another way to think
is that we popped it from callstack, and yet it still exists somewhere in the callstack already from prior call. Since we cant directly
access callstack.
ex: @ 1:06 (cycle between 0 and 1)
Here we are about to pop 0 from call stack and yet it still exists in call stack at bottom.
Since we are not able to directly access callstack , i think this is why
we use the 'visited' set.
visited { 0, 1}
| 1 | //pop from stack, BUT still exists in our visited set and callstack
| 0 |
| 1 |
this was a hard one, thanks for covering it. couldn't quite understand the solutions that people wrote on leetcode, but yours was pretty clear.
No problem
Thanks. :)
No problem Bellathor
On line 23. how does adjList[curr] === [] evalute to true???
-Yea that threw me off a a bit. Instead can replace with :
if (!adjList[course] || adjList[course].length == 0) {
return true //or simply just 'return'
}
-Or you can simply omit this conditional check as it isn't really compulsory.
Sorry it doesn't work on submission ,. there is some issue in adjacent list hat is being generated by your code. there might be some duplicate in my code but it works. @AlgoJS
can you pin
var canFinish = function (numCourses, prerequisites) {
let adajencyList = new Map();
let visited = new Set();
function addNode(airport) {
adajencyList.set(airport, []);
}
function addEdge(pre, post) {
adajencyList.get(post).push(pre);
}
let totalNodes = Array.from({ length: numCourses }, (v, i) => parseInt(i));
totalNodes.forEach(addNode);
prerequisites.forEach((pre) => addEdge(...pre));
function dfs(curr) {
if (visited.has(curr)) return false;
let child = adajencyList.get(curr);
visited.add(curr);
if (child.length !== 0) {
if (adajencyList.get(curr).length == 0) return true;
for (let index = 0; index < child.length; index++) {
if (!dfs(child[index])) return false;
}
}
visited.delete(curr);
adajencyList.set(curr, []);
return true;
}
for (let [key, value] of adajencyList) {
if (!dfs(key)) {
return false;
}
}
return true;
};