What makes course completion impossible?

A directed cycle creates circular dependency, so no valid completion order exists.

Can DFS and Kahn Algorithm both solve course scheduling?

Yes. DFS detects active-path cycles, while Kahn Algorithm checks whether all courses can be removed by indegree.

What happens when there are no prerequisites?

Return true because every course can be completed independently.

Course Schedule I | takeUforward

Given numCourses courses labeled from 0 to numCourses - 1 and a list of prerequisite pairs, return whether all courses can be finished.

Each pair [course, prerequisite] means the prerequisite course must be completed before the course. Completion is possible only when the prerequisite graph has no directed cycle.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: Course 0 can be completed before course 1.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: Course 0 and course 1 depend on each other, forming a cycle.

Approach 1

Each course becomes a vertex, and every pair creates a directed edge from prerequisite to dependent course. Depth First Search can detect whether a dependency chain returns to a course already active in the current DFS path.

A visited array tracks courses already explored globally, while a path-visited array tracks courses in the active recursion chain. Reaching a path-visited course means circular dependency, so completing every course becomes impossible.

Algorithm

Build an adjacency list with a directed edge from each prerequisite course to its dependent course.
Initialize visited and pathVisited arrays to track globally explored courses and courses in the current DFS path.
Traverse every course to cover all disconnected components.
Start DFS from each course that has not been visited.
Mark the current course as visited and pathVisited.
Run DFS for every unvisited dependent course and return false if any dependent course is already pathVisited.
Remove the current course from pathVisited after all its dependencies are processed.
Return true if no circular dependency is found.

Dry Run

course schedule

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5private:
6    // Detects a cycle through the active DFS path.
7    bool hasCycle(int course, vector<int>& visited, vector<int>& pathVisited, vector<vector<int>>& adj) {
8        // Mark the course as visited.
9        visited[course] = 1;
10
11        // Mark the course in the current DFS path.
12        pathVisited[course] = 1;
13
14        // Explore all courses depending on the current course.
15        for (int nextCourse : adj[course]) {
16            // Visit the next course if it is not visited.
17            if (!visited[nextCourse]) {
18                // If a cycle is found deeper, return true.
19                if (hasCycle(nextCourse, visited, pathVisited, adj)) {
20                    return true;
21                }
22            }
23
24            // If next course is in the current path, a cycle exists.
25            else if (pathVisited[nextCourse]) {
26                return true;
27            }
28        }
29
30        // Remove course from the active DFS path.
31        pathVisited[course] = 0;
32
33        // No cycle found from this course.
34        return false;
35    }
36
37public:
38    // Checks if all courses can be finished.
39    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
40        vector<vector<int>> adj(numCourses);
41
42        // Build edge from prerequisite to dependent course.
43        for (auto& pairValue : prerequisites) {
44            int course = pairValue[0];
45            int prerequisite = pairValue[1];
46
47            adj[prerequisite].push_back(course);
48        }
49
50        vector<int> visited(numCourses, 0);
51        vector<int> pathVisited(numCourses, 0);
52
53        // Start DFS from every unvisited course.
54        for (int course = 0; course < numCourses; course++) {
55            // Only unvisited courses can start a new DFS.
56            if (!visited[course]) {
57                // If a cycle exists, all courses cannot be finished.
58                if (hasCycle(course, visited, pathVisited, adj)) {
59                    return false;
60                }
61            }
62        }
63
64        // No circular dependency exists.
65        return true;
66    }
67};
68
69// Driver code.
70int main() {
71    int numCourses = 2;
72
73    vector<vector<int>> prerequisites = {
74        {1, 0}
75    };
76
77    Solution sol;
78
79    cout << (sol.canFinish(numCourses, prerequisites) ? "true" : "false");
80
81    return 0;
82}

Complexity Analysis

Time Complexity: O(V+E), where V is the number of courses and E is the number of prerequisite relations; DFS processes every course and directed edge once.

Space Complexity: O(V+E), where the adjacency list stores V courses and E edges, while the visited arrays and recursion stack require O(V) space.

Approach 2

Kahn Algorithm treats courses with indegree 0 as immediately available because no prerequisites block them. Completing such a course removes outgoing dependency effect from dependent courses.

If all courses can be processed through repeated zero-indegree removal, no cycle exists. If some courses never reach indegree 0, a circular dependency remains.

Algorithm

Build an adjacency list and an indegree array from all prerequisite pairs.
Add every course with indegree = 0 to a queue.
Initialize completed as 0.
Pop a course from the queue and increase completed.
Reduce the indegree of every dependent course.
Add a dependent course to the queue when its indegree becomes 0.
Continue until the queue becomes empty.
Return true if completed == numCourses; otherwise, return false.

Dry Run

1 / 2

Diagram 1

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    // Checks if all courses can be finished using Kahn's Algorithm.
7    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
8        vector<vector<int>> adj(numCourses);
9        vector<int> indegree(numCourses, 0);
10
11        // Build graph and indegree from prerequisites.
12        for (auto& pairValue : prerequisites) {
13            int course = pairValue[0];
14            int prerequisite = pairValue[1];
15
16            adj[prerequisite].push_back(course);
17            indegree[course]++;
18        }
19
20        queue<int> q;
21
22        // Add courses with no prerequisites.
23        for (int course = 0; course < numCourses; course++) {
24            // Zero indegree means this course can be completed now.
25            if (indegree[course] == 0) {
26                q.push(course);
27            }
28        }
29
30        int completed = 0;
31
32        // Complete courses in prerequisite-safe order.
33        while (!q.empty()) {
34            int course = q.front();
35            q.pop();
36
37            // Count the current course as completed.
38            completed++;
39
40            // Remove current course as prerequisite for dependent courses.
41            for (int nextCourse : adj[course]) {
42                indegree[nextCourse]--;
43
44                // If all prerequisites are done, add this course.
45                if (indegree[nextCourse] == 0) {
46                    q.push(nextCourse);
47                }
48            }
49        }
50
51        // All courses are possible only when all get completed.
52        return completed == numCourses;
53    }
54};
55
56// Driver code.
57int main() {
58    int numCourses = 2;
59
60    vector<vector<int>> prerequisites = {
61        {1, 0},
62        {0, 1}
63    };
64
65    Solution sol;
66
67    cout << (sol.canFinish(numCourses, prerequisites) ? "true" : "false");
68
69    return 0;
70}

Complexity Analysis

Time Complexity: O(V+E), where V is the number of courses and E is the number of prerequisite relations; every course and directed edge is processed once.

Space Complexity: O(V+E), where the adjacency list stores V courses and E edges, while the indegree array and queue require O(V) space.

Interview follow-up Questions

Courses are vertices, and prerequisite pairs are directed edges from prerequisite to dependent course.

Course Schedule I

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Disjoint Set Union: Union by Rank, Size and Path Compression

Print Shortest Path

Network Delay Time Using Dijkstra's Algorithm

Course Schedule I

Example 1

Example 2

Approach 1

Algorithm

Dry Run

Solution

Complexity Analysis

Approach 2

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why model course scheduling as a graph?

What makes course completion impossible?

Can DFS and Kahn Algorithm both solve course scheduling?

What happens when there are no prerequisites?

Read Similar Blogs

Disjoint Set Union: Union by Rank, Size and Path Compression

Print Shortest Path

Network Delay Time Using Dijkstra's Algorithm