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:

1. Create an adjacency list representation of the graph, where each node has a list of its outgoing edges.
2. Initialize a visited array to keep track of the nodes we have already visited, and a stack to keep track of the topological order.
3. 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.
4. 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.
5. 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; i

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?

 

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^5
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?

 

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;i

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 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; 
        }