Course Schedule

MediumGraphs

Given prerequisites between courses, return true if you can finish all courses, i.e. the dependency graph has no cycle.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000

Topological sort (Kahn's BFS)

Time O(V + E)Space O(V + E)

Build the graph with in-degrees. Repeatedly remove courses with zero remaining prerequisites and decrement their neighbors. If every course is removed, there is no cycle.

#include <bits/stdc++.h>
using namespace std;

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