This problem can be translated into finding cycles in a directed graph. Each course is a node, and a prerequisite is a directed edge from one course to another. If there is a cycle in the graph, it means there is no way to complete all courses because a course depends on itself indirectly.
To detect cycles, we perform a Depth First Search (DFS). We maintain a visitation state for each node: 0 = unvisited, 1 = visiting (currently in stack), and 2 = visited. During DFS, if we encounter a node that is already in the visiting state, it implies the presence of a cycle.
Time Complexity: O(V+E) where V is the number of courses and E is the number of prerequisites. We traverse each node and edge once.
Space Complexity: O(V+E) for the graph representation and recursion stack (in worst case).
1#include <stdbool.h>
2#include <stdlib.h>
3#include <string.h>
4#define MAX_COURSES 2000
5
6bool dfs(int course, int **graph, int *graphCol, int *visit) {
7 if (visit[course] == 1) return false;
8 if (visit[course] == 2) return true;
9
10 visit[course] = 1;
11 for (int i = 0; i < graphCol[course]; i++) {
12 if (!dfs(graph[course][i], graph, graphCol, visit))
13 return false;
14 }
15 visit[course] = 2;
16 return true;
17}
18
19bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize, int *prerequisitesColSize) {
20 int *graph[MAX_COURSES];
21 int graphCol[MAX_COURSES] = {0};
22 for (int i = 0; i < prerequisitesSize; i++) {
23 int course = prerequisites[i][0];
24 int prereq = prerequisites[i][1];
25 graph[prereq] = realloc(graph[prereq], sizeof(int) * (++graphCol[prereq]));
26 graph[prereq][graphCol[prereq] - 1] = course;
27 }
28
29 int visit[MAX_COURSES] = {0};
30 for (int i = 0; i < numCourses; i++) {
31 if (!dfs(i, graph, graphCol, visit))
32 return false;
33 }
34 return true;
35}In this C implementation, we represent the graph using adjacency lists. We dynamically grow these lists as prerequisites are added. The DFS is implemented using a helper function which checks for cycles using visitation states. If it detects a node in the 'visiting' state, a cycle is detected, and the function returns false.
Kahn's Algorithm provides an alternative way to perform a topological sort and can be employed to detect cycles. The idea is to repeatedly remove nodes with no incoming edges (no prerequisites) and reduce the incoming edges of each node's neighbors. If we are left with unvisited nodes, these form a cycle.
Initially, we compute the in-degree (number of incoming edges) for each node. Nodes with zero in-degree are added to a queue. We dequeue a node, add it to the topological order, and reduce the in-degree of its neighbors.
Time Complexity: O(V+E) where V is the number of courses and E is the number of prerequisites. Each node and edge are processed exactly once.
Space Complexity: O(V+E) for the graph and queue structures.
1var canFinish = function(numCourses, prerequisites) {
2 let inDegree = new Array(numCourses).fill(0);
3 let graph = Array.from({length: numCourses}, () => []);
4
5 for (let [course, prereq] of prerequisites) {
6 graph[prereq].push(course);
7 inDegree[course]++;
8 }
9
10 let zeroInDegreeQueue = [];
11 for (let i = 0; i < numCourses; i++) {
12 if (inDegree[i] === 0) zeroInDegreeQueue.push(i);
13 }
14
15 let visitedCourses = 0;
16 while (zeroInDegreeQueue.length) {
17 let course = zeroInDegreeQueue.shift();
18 visitedCourses++;
19
20 for (let neighbor of graph[course]) {
21 inDegree[neighbor]--;
22 if (inDegree[neighbor] === 0) {
23 zeroInDegreeQueue.push(neighbor);
24 }
25 }
26 }
27
28 return visitedCourses === numCourses;
29};This JavaScript solution tracks the in-degrees of each course using an array. Courses with zero in-degree are processed first. Each removal of a node might generate new nodes with zero in-degree, which are then processed. By the end, if all nodes are processed, it is possible to complete all courses; otherwise, a cycle exists.