210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

Course Schedule II - LeetCode

 

// ___________________문제___________________

// 모든 경로를 탐색하며 레벨을 올라가기

 

// __________________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

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 : [];

};