Sponsored
Sponsored
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).
1def canFinish(numCourses, prerequisites):
2 from collections import defaultdict
3
4 def dfs(course):
5 if visit[course] == 1:
6 return False
7 if visit[course] == 2:
8 return True
9
10 visit[course] = 1
11 for prereq in graph[course]:
12 if not dfs(prereq):
13 return False
14 visit[course] = 2
15 return True
16
17 graph = defaultdict(list)
18 for course, prereq in prerequisites:
19 graph[course].append(prereq)
20
21 visit = [0] * numCourses
22 for course in range(numCourses):
23 if not dfs(course):
24 return False
25 return TrueWe utilize a recursion stack to perform DFS on each node. When a node is being processed, it is marked as 'visiting'. If during the traversal we encounter a node that is already marked 'visiting', a cycle is present, and we return False. After processing, nodes are marked 'visited'. This implementation correctly detects cycles in the directed graph of course dependencies.
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.
1import java.util.*
In this Java implementation of Kahn's Algorithm, we initialize in-degrees for all courses. Nodes with zero in-degree are processed first. Processing involves adding them to an output list and decreasing the in-degree of their neighboring nodes. If a neighboring node's in-degree drops to zero, it becomes eligible for processing next.