210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/
Course Schedule II - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
// ___________________문제___________________
// 모든 경로를 탐색하며 레벨을 올라가기
// __________________Syntax__________________
//
// ________________Algorithms________________
//
// ____________________Input___________________
// prerequisites: [[4, 2], [4, 1], [2, 3], [2, 1], [3, 0], [2, 0], [1, 0]];
// prerequisites: [[1,0],[2,1],[0,2]];
1. 내 풀이
let graph;
let visited;
let visiting;
var findOrder = function (numCourses, prerequisites) {
graph = new Map();
visited = new Set();
visiting = new Set();
let allNumbers = new Set();
for ([e, s] of prerequisites) {
let edges = graph.get(e) || [];
edges.push(s);
graph.set(e, edges);
allNumbers.add(s);
allNumbers.add(e);
}
for(let i = 0; i < numCourses; i++) {
if(allNumbers.has(i)) {
continue;
}
visited.add(i);
}
for ([e, s] of graph) {
let hasCycle = backTracking(e);
if(hasCycle === false) {
return [];
}
}
return [...visited];
};
var backTracking = function (node) {
let edges = graph.get(node);
visiting.add(node);
if (edges) {
for (s of edges) {
if (visited.has(s)) {
continue;
} else if (visiting.has(s)) {
return false;
}
let hasCycle = backTracking(s);
if(hasCycle === false) {
return false;
}
}
}
visiting.delete(node);
visited.add(node);
}
2. https://leetcode.com/problems/course-schedule-ii/discuss/420402/Clean-JavaScript-solution
Clean JavaScript solution - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
const findOrder = (numCourses, prerequisites) => {
const inDegrees = new Array(numCourses).fill(0);
// [0, 1, 2, 1, 2]
for (const [v] of prerequisites) {
inDegrees[v]++;
}
const q = [];
for (let i = 0; i < inDegrees.length; i++) {
const degree = inDegrees[i];
if (degree === 0) q.push(i);
}
const res = [];
while (q.length) {
const u0 = q.shift();
numCourses--;
res.push(u0);
for (const [v, u] of prerequisites) {
if (u === u0) {
inDegrees[v]--;
if (inDegrees[v] === 0) q.push(v);
}
}
}
return numCourses === 0 ? res : [];
};