Course Schedule

This is the solution for the Leetcode problem Course Schedule. With a little modification we can also solve Couse Schedule II , where we need to order the courses in the manner of their dependencies.

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

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.

The problem basically is related to a bunch of dependencies. We have to find out if it is possible to finish all courses keeping their dependency relationships in mind.

Algorithm Used

The algorithm we will be using is Kahn’s algorithm for topological sorting. This problem is essentially a topological sorting problem which can be solved by either of the graph traversals. We are gonna solve it using Kahn’s algorithm as this algorithm implicitly detects cycles in the graph if present. This problem involves directed graph to represent the dependencies.

Solution

We will be using adjacent list as a means to represent a graph. The solution mainly involves:-

1. Creation of an indegree array to represent the indegrees of all the nodes. Calculation of initial set of nodes with indegrees as 0, which will be our starting nodes and will be processed first.
2. Population of our Queue data structure with the nodes with indegree count as 0 and traversing the neighboring nodes in the Breadth First Search manner. Whenever we encounter any node we will decrease its indegree by one as one of the edge we traversed to reach it. If its indegree count becomes 0 we enqueue in our queue.
3. The count variable takes care of our visited nodes. If count is same as our node count there is no cycle, if not we have a cycle in the graph.

Code

public class Solution {
    List<int>[] adjacencyList;
    private void AddEdge(int src,int dest)
    {
        // adding edge to constuct our adjacency list
        adjacencyList[src].Add(dest);
    }
    public bool CanFinish(int numCourses, int[][] prerequisites) 
    {
        adjacencyList = new List<int>[numCourses];
        for(int i = 0 ; i < numCourses ; i++)
        {
            adjacencyList[i] = new List<int>();
        }
        for(int i = 0 ; i < prerequisites.Length ; i++)
        {
            AddEdge(prerequisites[i][1],prerequisites[i][0]);
        }
        
        // Ititialising our indegree array
        int[] indegree = new int[numCourses];
        foreach(var item in adjacencyList)
        {
            foreach(int course in item)
            {
                indegree[course]++;
            }
        }
        // Populating the queue with the starting nodes who do not have an incoming edge
        Queue<int> queue = new Queue<int>();
        for(int i = 0 ; i < numCourses ; i++)
        {
            if(indegree[i] == 0)
            {
                queue.Enqueue(i);
            }
        }
        int count = 0;
        while(queue.Count != 0)
        {
            int curr = queue.Dequeue();
            count++;
            foreach(var item in adjacencyList[curr])
            {
                if(--indegree[item] == 0)
                {
                    queue.Enqueue(item);
                }
            }
        }
        // Check to see if the graph has a cycle
        if(count == numCourses)
        {
            return true;
        }
        return false;
    }
}

Time Complexity O(|E| + |V|), Space Complexity O(|E|+|V|).