Course Schedule — Cycle Detection BFS/DFS

Problem

There are numCourses courses. Prerequisites are pairs [a,b] meaning 'must take b before a'. Can you finish all courses?

Equivalent to: Is the directed graph a DAG (no cycle)?

Approach 1 — BFS Topological Sort (Kahn's)

Compute in-degrees. Start with nodes of in-degree 0. Process queue, decrement neighbours; if they hit 0 add to queue. Count processed nodes.

Approach 2 — DFS Cycle Detection

Color nodes: 0=unvisited, 1=in-stack, 2=done. If we hit a node colored 1, cycle found.

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

Solutions

Python — BFS Kahn's

from collections import deque
class Solution:
    def canFinish(self, n: int, prereqs: list[list[int]]) -> bool:
        adj=[[] for _ in range(n)]; indeg=[0]*n
        for a,b in prereqs: adj[b].append(a); indeg[a]+=1
        q=deque(i for i in range(n) if indeg[i]==0)
        count=0
        while q:
            node=q.popleft(); count+=1
            for nb in adj[node]:
                indeg[nb]-=1
                if indeg[nb]==0: q.append(nb)
        return count==n

Python — DFS Coloring

class Solution:
    def canFinish(self, n: int, prereqs: list[list[int]]) -> bool:
        adj=[[] for _ in range(n)]; color=[0]*n
        for a,b in prereqs: adj[b].append(a)
        def dfs(u):
            if color[u]==1: return False
            if color[u]==2: return True
            color[u]=1
            for v in adj[u]:
                if not dfs(v): return False
            color[u]=2; return True
        return all(dfs(i) for i in range(n))

C++

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

Java

class Solution {
    public boolean canFinish(int n, int[][] pre){
        List<List<Integer>> adj=new ArrayList<>();
        int[] indeg=new int[n];
        for(int i=0;i<n;i++) adj.add(new ArrayList<>());
        for(int[] p:pre){adj.get(p[1]).add(p[0]);indeg[p[0]]++;}
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<n;i++) if(indeg[i]==0) q.add(i);
        int cnt=0;
        while(!q.isEmpty()){
            int u=q.poll();cnt++;
            for(int v:adj.get(u)) if(--indeg[v]==0) q.add(v);
        }
        return cnt==n;
    }
}

Complexity

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