Determine a way to take n college courses in order, from course 0 to n-1. However, some courses can have multiple prerequisites. Provide any possible order or [-1] if there's no solution.
Question Explain
This question regards a type of problem known as topological sorting in graph theory. Essentially, the task is to order a set of vertices in a directed acyclic graph (DAG). In this case, the vertices are the college courses (numbered from 0 to n-1) and a directed edge from course A to course B signifies that course A is a prerequisite for course B. Courses can have multiple prerequisites, which means that a single course can have multiple incoming edges.
The question asks for an implementation of a course order that satisfies all prerequisites or return [-1] if it is impossible to take all courses due to circular prerequisite dependencies (which violates the DAG condition).
We can approach this problem using Depth First Search (DFS) or Breadth First Search (BFS):
-
Generate a graph from the input, where the nodes represent the courses and the edges represent the prerequisite relationships.
-
Use DFS or BFS to traverse the graph:
-
If you use DFS, make sure to detect cycles and stop traversing further if a cycle is detected.
-
If you use BFS, start with nodes that have no prerequisites. After processing a node, add it to the result and decrease the prerequisite count for its children.
- If all courses are covered in the traversal (meaning there was no cycle), return the ordering, else return [-1].
Answer Example 1
Here is an approach using BFS (Also known as Kahn's algorithm) in Python:
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
indegrees = defaultdict(int)
for u, v in prerequisites:
graph[v].append(u)
indegrees[u] += 1
dq = deque([u for u in range(numCourses) if indegrees[u] == 0])
result = []
while dq:
v = dq.popleft()
result.append(v)
for u in graph[v]:
indegrees[u] -= 1
if indegrees[u] == 0:
dq.append(u)
return result if len(result) == numCourses else [-1]
Answer Example 2
An approach using DFS could be as follows in Python:
from collections import defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
for u, v in prerequisites:
graph[v].append(u)
visited = [0 for _ in range(numCourses)]
stack = []
for course in range(numCourses):
if not dfs(course, graph, visited, stack):
return [-1]
return stack[::-1]
def dfs(course, graph, visited, stack):
if visited[course] == -1:
return False
if visited[course] == 1:
return True
visited[course] = -1
for pre in graph[course]:
if not dfs(pre, graph, visited, stack):
return False
visited[course] = 1
stack.append(course)
return True
In this DFS version, a course is marked as -1
during the DFS from this course and marked as 1
after the DFS from this course. If at any point in DFS we meet a course that is marked as -1
, it means that the graph contains a cycle and we return False
. If no cycles are detected, we mark the node as fully traversed (1
) and add it to the end of our course schedule (stack).