Course Schedule

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(n);
        vector<int> indeg(n, 0);
        for (auto& p : prerequisites) {
            adj[p[1]].push_back(p[0]);
            ++indeg[p[0]];
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
        int taken = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ++taken;
            for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
        }
        return taken == n;
    }
};

func canFinish(n int, prerequisites [][]int) bool {
    adj := make([][]int, n)
    indeg := make([]int, n)
    for _, p := range prerequisites {
        adj[p[1]] = append(adj[p[1]], p[0])
        indeg[p[0]]++
    }
    q := []int{}
    for i := 0; i < n; i++ {
        if indeg[i] == 0 {
            q = append(q, i)
        }
    }
    taken := 0
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        taken++
        for _, v := range adj[u] {
            indeg[v]--
            if indeg[v] == 0 {
                q = append(q, v)
            }
        }
    }
    return taken == n
}

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for course, prereq in prerequisites:
            adj[prereq].append(course)
            indeg[course] += 1
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        taken = 0
        while q:
            u = q.popleft()
            taken += 1
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return taken == numCourses

function canFinish(numCourses, prerequisites) {
    const adj = Array.from({ length: numCourses }, () => []);
    const indeg = new Array(numCourses).fill(0);
    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        indeg[course]++;
    }
    const q = [];
    for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
    let taken = 0;
    while (q.length) {
        const u = q.shift();
        taken++;
        for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
    }
    return taken === numCourses;
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return taken == numCourses;
    }
}

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const adj: number[][] = Array.from({ length: numCourses }, () => []);
    const indeg: number[] = new Array(numCourses).fill(0);
    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        indeg[course]++;
    }
    const q: number[] = [];
    for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
    let taken = 0;
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        taken++;
        for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
    }
    return taken === numCourses;
}