207. Course schedule

course-schedule.js

"use strict";
class Graph {
    #InitialCourses;
    constructor(edges) {
        this.E = new Map();
        this.V = new Set();
        this.I = new Map();
        this.#InitialCourses = [];
        if (edges.length === 0) {
            return;
        }
        edges.forEach(edge => {
            const [a, b] = edge;
            // adding vertices
            this.V.add(a);
            this.V.add(b);
            // setting up indegree
            this.I.set(a, this.I.get(a) || 0);
            this.I.set(b, (this.I.get(b) || 0) + 1);
            // setting up edge
            if (!this.E.has(a)) {
                this.E.set(a, new Set());
            }
            this.E.get(a).add(b);
        });
    }
    get initialCourses() {
        if (this.#InitialCourses.length > 0) {
            return this.#InitialCourses;
        }
        const queue = [];
        this.I.forEach((indegree, course) => {
            if (indegree === 0) {
                queue.push(course);
            }
        });
        this.#InitialCourses = queue;
        return this.#InitialCourses;
    }
    get count() {
        let c = 0;
        const queue = [...this.initialCourses];
        while (queue.length > 0) {
            const current = queue.shift();
            c++;
            this.E.get(current)?.forEach(course => {
                const indegree = this.I.get(course);
                const newIndegree = indegree - 1;
                this.I.set(course, newIndegree);
                if (newIndegree === 0) {
                    queue.push(course);
                }
            });
        }
        return c;
    }
}
/**
 * @example
 * numCourses
 */
function canFinish(numCourses, prerequisites) {
    if (prerequisites.length === 0) {
        return true;
    }
    if (numCourses < 2) {
        return !!numCourses;
    }
    const g = new Graph(prerequisites);
    // console.log(g, g.initialCourses);
    if (g.initialCourses.length === 0) {
        return false;
    }
    return g.V.size === g.count;
}
;

course-schedule.ts

/**
    E: edges
    V: vertices
    I: indegree counter
 */
type GraphT = {
    E: Map<number, Set<number>>;
    V: Set<number>;
    I: Map<number, number>;
}

class Graph implements GraphT {
    E: Map<number, Set<number>>;
    V: Set<number>;
    I: Map<number, number>;
    #InitialCourses: number[];

    constructor(edges: number[][]) {
        this.E = new Map<number, Set<number>>();
        this.V = new Set<number>();
        this.I = new Map<number, number>();
        this.#InitialCourses = [];

        if (edges.length === 0) {
            return;
        }

        edges.forEach(edge => {
            const [a, b] = edge;
            // adding vertices
            this.V.add(a);
            this.V.add(b);
            // setting up indegree
            this.I.set(a, this.I.get(a) || 0)
            this.I.set(b, (this.I.get(b) || 0) + 1);
            // setting up edge
            if (!this.E.has(a)) {
                this.E.set(a, new Set<number>());
            }
            this.E.get(a)!.add(b);
        });
    }

    get initialCourses() {
        if (this.#InitialCourses.length > 0) {
            return this.#InitialCourses;
        }
        const queue: number[] = [];
        this.I.forEach((indegree, course) => {
            if (indegree === 0) {
                queue.push(course);
            }
        });
        this.#InitialCourses = queue;
        return this.#InitialCourses;
    }

    get count() {
        let c = 0;
        const queue = [...this.initialCourses];
        while (queue.length > 0) {
            const current = queue.shift();
            c++;

            this.E.get(current)?.forEach(course => {
                const indegree = this.I.get(course);
                const newIndegree = indegree - 1;
                this.I.set(course, newIndegree);
                if (newIndegree === 0) {
                    queue.push(course);
                }

            })
        }
        return c;
    }
}

/**
 * @example
 * numCourses
 */
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    if (prerequisites.length === 0) {
        return true;
    }
    if (numCourses < 2) {
        return !!numCourses;
    }
    const g = new Graph(prerequisites);
    // console.log(g, g.initialCourses);
    if (g.initialCourses.length === 0) {
        return false;
    }

    return g.V.size === g.count;
};