Course Schedule Topological Sort DSA Solution - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 7: Graphs

Learning Outcome

After this lesson, you should be able to model prerequisites as a directed graph and use zero-indegree BFS to detect cycles.

Problem Statement

Given numCourses and prerequisite pairs, return true if all courses can be finished.

Brute Force Approach

Try every possible course order. This is factorial in the number of courses and quickly becomes impossible.

Optimized Approach

Build a directed graph from prerequisite to course. Repeatedly take courses with indegree 0 and count how many courses are removed.

Exact Pseudocode

build graph and indegree
queue = all courses with indegree 0
taken = 0
while queue not empty:
  course = pop front
  taken += 1
  for nextCourse in graph[course]:
    indegree[nextCourse] -= 1
    if indegree[nextCourse] becomes 0:
      push nextCourse
return taken equals numCourses

Reference Code

from collections import deque

class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1

        q = deque(i for i in range(numCourses) if indegree[i] == 0)
        taken = 0

        while q:
            course = q.popleft()
            taken += 1
            for nxt in graph[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    q.append(nxt)

        return taken == numCourses

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);

        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);
        }

        int taken = 0;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            taken++;
            for (int nxt : graph[course]) {
                indegree[nxt]--;
                if (indegree[nxt] == 0) q.push(nxt);
            }
        }

        return taken == numCourses;
    }
};

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[numCourses];

        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.offer(i);
        }

        int taken = 0;
        while (!q.isEmpty()) {
            int course = q.poll();
            taken++;
            for (int nxt : graph.get(course)) {
                indegree[nxt]--;
                if (indegree[nxt] == 0) q.offer(nxt);
            }
        }

        return taken == numCourses;
    }
}

Sample Dry Run

Complexity

Edge Cases

• No prerequisites should return true.
• A cycle leaves some courses with positive indegree.
• Edge direction must be prerequisite to course.

Interview Checklist

• Build indegree from course dependencies.
• Start with all zero-indegree courses.
• Compare taken count with numCourses.

FAQs

Every course in the cycle waits for another course in the same cycle, so none reaches indegree 0.

Yes. DFS cycle detection with visiting states is another standard solution.

Topological sort using Kahn BFS.

Tags

• dsa
• graphs
• topological sort