1. Topological Sort

class prerequisites

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• All the pairs prerequisites[i] are unique.

Loading...LeetCode

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const incommingEdges = new Array(numCourses).fill(0);
    const adjs = {};

    // create adjacent listx
    // couting num of edges incomming
    for (const [here, there] of prerequisites) {
        if (adjs[here] === undefined) adjs[here] = [];
        adjs[here].push(there);

        incommingEdges[there] += 1;
    }

    const q = [];
    // find vertexes incomming edges 0
    for (let i = 0; i < incommingEdges.length; i++) {
        if (incommingEdges[i] === 0) {
            q.push(i);
        }
    }

    // iterate queue until there is no vertex, whose the number of incomming edges is equal to zero
    const seq = [];
    while (q.length > 0) {
        const here = q.shift();
        seq.push(here);
        const adj = adjs[here] ?? [];

        // if (adj === undefined) continue;

        for (const there of adj) {
            incommingEdges[there] -= 1;
            if (incommingEdges[there] === 0) {
                q.push(there);
            }
        }
    }

    return seq.length === numCourses ? true : false;
    
};