Solution For Course Schedule
The Course Schedule problem on LeetCode (Problem No. 207) asks us to determine whether it is possible to complete all the courses in a given set of prerequisites.
The problem statement and input format can be found on the LeetCode website. The problem essentially boils down to checking whether the given set of prerequisite relationships forms a directed acyclic graph (DAG). If there is a cycle in the graph, it means that there is a circular dependence between courses, and we cannot complete all the courses.
One way to approach this problem is to use a topological sort algorithm on the given directed graph. A topological sort of a DAG is a linear ordering of its nodes such that for every directed edge (u, v), node u comes before node v in the ordering. If the graph has a topological order, it means that there is no circular dependence between its nodes.
We can implement a topological sort using a modified depth-first search (DFS) algorithm. The idea behind the algorithm is as follows:
Create an adjacency list representation of the graph, where each node has a list of its outgoing edges.
Initialize a visited array to keep track of the nodes we have already visited, and a stack to keep track of the topological order.
For each unvisited node in the graph, call a DFS function that explores all its outgoing edges and adds the node to the stack after visiting all its neighbors.
If we encounter a visited node during the DFS function, it means that there is a cycle in the graph, and we can return False.
If we have visited all the nodes in the graph without encountering a cycle, it means that we have a valid topological order, and we can return True.
Here is the Python code for the solution as explained above:
“`
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# Step 1: Create adjacency list representation of the graph
graph = defaultdict(list)
for pair in prerequisites:
graph[pair[1]].append(pair[0])
# Step 2: Initialize visited and stack arrays
visited = [False] * numCourses
stack = [False] * numCourses
# Step 3: Call DFS function for each unvisited node
for node in range(numCourses):
if not visited[node]:
if self.hasCycle(node, graph, visited, stack):
return False
# Step 5: If we reach here, the graph is acyclic
return True
# Helper function for DFS traversal of the graph
def hasCycle(self, node: int, graph: defaultdict(list), visited: List[bool], stack: List[bool]) -> bool:
# Mark current node as visited and add to stack
visited[node] = True
stack[node] = True
# Recursively visit all neighbors of current node
for neighbor in graph[node]:
if not visited[neighbor]:
if self.hasCycle(neighbor, graph, visited, stack):
return True
elif stack[neighbor]:
return True
# Remove current node from stack after visiting all its neighbors
stack[node] = False
# If we reach here, there is no cycle in the current subgraph
return False
“`
The time complexity of the algorithm is O(N + E), where N is the number of nodes and E is the number of edges in the graph. This is because we visit each node and edge in the graph exactly once. The space complexity is also O(N + E), because we use adjacency list representation of the graph and other auxiliary arrays.
In conclusion, the Course Schedule problem on LeetCode can be solved using a topological sort algorithm based on DFS. We check for cycles in the graph during the DFS traversal, and return False if a cycle is found. Otherwise, we return True if the graph is acyclic.
Step by Step Implementation For Course Schedule
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
public boolean canFinish(int numCourses, int[][] prerequisites) {
//Create an array of ArrayList's to store what courses depend on the course
//indexed by the row number
ArrayList[] courseDependencies = new ArrayList[numCourses];
//Initialize each course's dependencies list
for(int i=0; i();
}
//For each prerequisite pair, add the course that must be completed first
//to the list of dependencies for the course that it is a prerequisite for
for(int i=0; i[] courseDependencies, boolean[] visited, boolean[] partOfCycle) {
//If the course has already been visited, and it is not part of a cycle, return false
if(visited[course] && !partOfCycle[course]) {
return false;
}
//If the course has already been visited, and it is part of a cycle, return true
if(visited[course] && partOfCycle[course]) {
return true;
}
//Set the course to visited
visited[course] = true;
//For each course that the current course depends on,
//check if it is part of a cycle
for(int i=0; iThere are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Constraints:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
class Solution {
public:
bool canFinish(int numCourses, vector>& prerequisites) {
//Create a graph
unordered_map> graph;
//Create a visited array
vector visited(numCourses,false);
//Create a recStack array
vector recStack(numCourses,false);
//Loop through the prerequisites array and fill up the graph
for(int i=0;i>& graph, int course, vector& visited, vector& recStack)
{
//Mark the course as visited
visited[course]=true;
//Mark the course as present in the recursion stack
recStack[course]=true;
//Loop through all the courses that are prerequisites for the current course
for(int i=0;iThere are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
public bool CanFinish(int numCourses, int[][] prerequisites)
{
// Create a graph
Dictionary> adj = new Dictionary>();
for (int i = 0; i < numCourses; i++)
adj.Add(i, new List());
// Add edges to the directed graph
for (int i = 0; i < prerequisites.Length; i++)
adj[prerequisites[i][1]].Add(prerequisites[i][0]);
// Mark all the vertices as not visited and
// not part of recursion stack
bool[] visited = new bool[numCourses];
bool[] recStack = new bool[numCourses];
// Call the recursive helper function
// to detect cycle in different DFS trees
for (int i = 0; i < numCourses; i++)
if (IsCyclic(adj, i, visited, recStack))
return false;
return true;
}
private bool IsCyclic(Dictionary> adj, int v, bool[] visited,
bool[] recStack)
{
if (recStack[v])
return true;
if (visited[v])
return false;
visited[v] = true;
recStack[v] = true;
List children = adj[v];
foreach (var c in children)
if (IsCyclic(adj, c, visited, recStack))
return true;
recStack[v] = false;
return false;
}