Sponsored
Sponsored
Consider courses as nodes in a directed graph, and prerequisites as directed edges. We can apply Kahn's algorithm for topological sorting to find the order of courses to take. The algorithm works by using an in-degree array that tracks the number of prerequisites for each course. Courses with zero in-degrees can be taken immediately. As our course order is populated, we decrement the in-degree of their dependent courses, allowing them to be taken in subsequent steps.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph and the in-degree array.
1from collections import deque, defaultdict
2
3def findOrder(numCourses, prerequisites):
4 in_degree = [0] * numCourses
5 graph = defaultdict(list)
6
7 for course, prereq in prerequisites:
8 graph[prereq].append(course)
9 in_degree[course] += 1
10
11 queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
12 order = []
13
14 while queue:
15 node = queue.popleft()
16 order.append(node)
17 for neighbor in graph[node]:
18 in_degree[neighbor] -= 1
19 if in_degree[neighbor] == 0:
20 queue.append(neighbor)
21
22 return order if len(order) == numCourses else []
23This solution uses a breadth-first search (BFS) starting from courses with zero prerequisites. As courses are completed, they are removed from their neighbors' prerequisites, enabling further courses to be completed in order. This ensures the result represents a valid topological sort of the course schedule.
Similar to the Kahn's algorithm approach, but using a depth-first search (DFS) to detect cycles and determine the order of courses. In this method, courses are visited, and if a course is revisited while still in the recursion stack, it indicates a cycle, making course completion impossible. The order is determined by recording the exit point of each node during the DFS.
Time Complexity: O(V + E), where V is the number of courses, and E is the number of prerequisites.
Space Complexity: O(V + E), where V and E account for the graph structure and visited array.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] FindOrder(int numCourses, int[][] prerequisites) {
List<int>[] graph = new List<int>[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new List<int>();
foreach (var prereq in prerequisites) graph[prereq[1]].Add(prereq[0]);
bool[] visited = new bool[numCourses];
bool[] recStack = new bool[numCourses];
List<int> order = new List<int>();
for (int i = 0; i < numCourses; i++) {
if (HasCycle(graph, visited, recStack, i, order))
return new int[0];
}
order.Reverse();
return order.ToArray();
}
private bool HasCycle(List<int>[] graph, bool[] visited,
bool[] recStack, int node, List<int> order) {
if (recStack[node]) return true;
if (visited[node]) return false;
visited[node] = true;
recStack[node] = true;
foreach (int neighbor in graph[node])
if (HasCycle(graph, visited, recStack, neighbor, order))
return true;
recStack[node] = false;
order.Add(node);
return false;
}
}
The C# solution leverages DFS to topologically sort the courses while simultaneously checking for cycles. The recursion stack helps identify cycles, while completed nodes are added to a list in post-order to establish the course sequence.