Tags

AWS (7)

Apigee (3)

ArchLinux (5)

Array (6)

Backtracking (6)

BinarySearch (6)

C++ (19)

CI&CD (3)

Calculus (2)

DesignPattern (43)

DisasterRecovery (1)

Docker (8)

DynamicProgramming (20)

FileSystem (11)

Frontend (2)

FunctionalProgramming (1)

GCP (1)

Gentoo (6)

Git (15)

Golang (1)

Graph (10)

GraphQL (1)

Hardware (1)

Hash (1)

Kafka (1)

LinkedList (13)

Linux (27)

Lodash (2)

MacOS (3)

Makefile (1)

Map (5)

MathHistory (1)

MySQL (21)

Neovim (10)

Network (66)

Nginx (6)

Node.js (33)

OpenGL (6)

PriorityQueue (1)

ProgrammingLanguage (9)

Python (10)

RealAnalysis (20)

Recursion (3)

Redis (1)

RegularExpression (1)

Ruby (19)

SQLite (1)

Sentry (3)

Set (4)

Shell (3)

SoftwareEngineering (12)

Sorting (2)

Stack (4)

String (2)

SystemDesign (13)

Terraform (2)

Tree (24)

Trie (2)

TwoPointers (16)

TypeScript (3)

Ubuntu (4)

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.

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.

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const graph: Map<number, number[]> = new Map<number, number[]>();
    const visited: Set<number> = new Set<number>();
    
    // construct map
    for(const [course, pre] of prerequisites){
        const preList: number[] = graph.get(course) || [];
        preList.push(pre);
        graph.set(course, preList);
    }
    
    // DFS cycle detection
    const hasCycle = (node: number): boolean => {
        // base case
        if(visited.has(node)) {
            return true;
        }
        
        // visit node
        visited.add(node)
        const neighbours = graph.get(node) || []
        for(let neighbour of neighbours){
            if(hasCycle(neighbour)){
                return true
            }
        }
        // unvisited node
        visited.delete(node)
        // no repeated work later
        graph.set(node, [])
        
        return false
    }
    
    for(let i = 0; i < numCourses; i++){
        if(hasCycle(i)){
            return false;
        }
    }
    
    return true;
};

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    let finishedCourses = 0;
    
    let coursePreCount: number[] = [];
    const queue: number[] = [];
    const graph: Map<number, number[]> = new Map<number, number[]>()
    
    // init pres and graph
    for(let i = 0; i < numCourses; i++){
        coursePreCount[i] = 0;
        graph[i] = []
    }
    
    // update pres and graph
    for(const [course, pre] of prerequisites){
        coursePreCount[course]++
        graph[pre].push(course)
    }
    
    // start course with no pres
    for(let i = 0; i < numCourses; i++){
        if(coursePreCount[i] === 0){
            queue.push(i)
        }
    }
    
    // let's start BFS
    while(queue.length > 0){
        const course = queue.shift();
        
        finishedCourses++
        if(finishedCourses === numCourses) {
            return true
        }
        
        for(let node of graph[course]){
            coursePreCount[node]--;
            if(coursePreCount[node] === 0){
                queue.push(node);
            }
        }
    }
    
    return false;
};