A certain university has n courses to offer and to graduate from that university, a student must complete all of the courses. Some of the courses have a set of prerequisite courses. One can take a course only after completing all of its prerequisites. Dependencies between the courses are described by two arrays a and b of the same size: course a[i] must be taken before course b[i] for all valid indices. Is it possible to complete all the courses without violating constraints?

‍

Example One

Input: n = 4, a = [1, 1, 3], b = [0, 2, 1]

Output: true

One possible ordering is 3, 1, 0, 2.

‍

Example Two

Input: n = 4, a = [1, 1, 3, 0], b = [0, 2, 1, 3]

Output: false

Every possible ordering of the courses violates at least one of the constraints.

‍

Notes

The courses are labelled from 0 to n - 1.

Constraints:

● 2

● 1

● 0

● a[i] != b[i] holds for any valid index i

● No duplicate dependencies

‍

Solution

We have provided two solutions.

First, we shall model the constraints and the courses as a graph and then develop one solution using depth-first search(DFS) and another solution using Kahn's algorithm.

Let us imagine a graph of n nodes where node i represents course labeled i. If course x must be completed before taking course y, then imagine a directed edge from x to y to represent their dependency. Let m be equal to the number of edges in the graph.

if the above graph has a cycle, then we would not be able to complete any course from that cycle due to cyclic dependency. On the other hand, it can be proven that it will always be possible to complete all of the courses if the above graph is acyclic.

Proof: A node without any incoming edges must exist in a graph for it to be acyclic. It implies that the course which is represented by that node can be completed as it has no prerequisites. If there are more than one such course then we can complete all of them in any order. After completing a course, we can remove the node representing the course and all of its outgoing edges as those constraints no longer exist. After removing that node & its edges, we are left with another, smaller acyclic graph. We can apply the same arguments for the reduced graph and keep eliminating the nodes until we are left with an empty graph. Empty graph would imply that all of the courses have been completed.

So the problem reduces to finding whether the above directed graph has a cycle or not.

‍

1) dfs_solution

Here we have described an algorithm to detect cycles in a directed graph using depth-first search.

During a depth-first traversal of the graph every node of the graph is visited exactly once. So for every node in the graph, a DFS call will be initiated once for that node. The nodes can be in one of the following three states.

● Undiscovered: The set of nodes for which no DFS call has been initiated yet, belongs to this state. Initially all the nodes are undiscovered.

● Discovered and finished processing: A node is considered to be discovered when a DFS call has been initiated for that node. A node is considered to have finished processing when the DFS function call for that particular node gets popped from the recursion call stack.

● Discovered and still being processed: The nodes that have been discovered but the DFS function calls for those nodes are still in the call stack, possess this state.

We will be coloring the nodes with white, black and grey color respectively to represent the above states. Initially all of the nodes will be colored white. Upon discovering a node, it will be colored grey. Just before the termination of the DFS call for a particular node, we will color that node in black.

Our solution with a depth-first search has the following steps:

● Iterate through the given edges and form adjacency list of the graph. This will help us run the depth-first search(DFS) in O(n + m) complexity.

● Initiate a DFS call from every undiscovered node in the graph in any order.

● Check the existence of any cycle: Inside the DFS call for a node, we loop over its neighbours and initiate a DFS call for each of its undiscovered neighbours. We can claim that the given graph has a cycle if inside the DFS call for a node, it discovers a grey neighbour. Such an edge between two grey nodes is known as a back edge.

If no cycle gets reported during the depth-first search traversal, we can claim that all of the courses can be completed.

Time Complexity:

O(n + m).

For creating adjacency list: O(m).

For running DFS:  O(n + m).

So total time complexity: O(n + m).

Auxiliary Space Used:

O(n + m).

For storing adjacency list: O(m).

For storing the state/color of the vertices during DFS: O(n).

For the call stack of the DFS function call: O(n).

So, total auxiliary space used: O(n + m).

Space Complexity:

O(n + m).

Space used for input: O(m).

Space used for output: O(1).

Auxiliary space used: O(n + m).

So total space complexity: O(n + m).

‍

1) kahns_algorithm_solution

Here we have described the Kahn's algorithm for topological sorting by in-degree tracking.

Let us maintain a queue q. A course's label will be in this queue if all of its prerequisite courses have been completed but we have not completed this course yet. Let us also maintain another array indegree, where indegree[i] would store the number of prerequisite courses which are yet to be taken before taking the course labeled i. Initially, indegree[i] would be equal to the indegree of node label i in the graph. To maintain the invariant on the queue q, let us insert the labels i in the queue if indegree[i] == 0 holds for all valid index i. Let us also iterate through the given dependencies and store the labels of the courses which can only be completed after completing the course labeled i for all valid i.

As long as the queue is not empty, our course of action will be:

● Take the front element of the queue.

● Complete that course.

● Reduce the indegree of the courses which were dependent on this course.

● If after reducing the indegree value, any of the courses’ indegree value reaches 0 - then push it to the queue.  

If after the termination of our algorithm, we are left with any uncompleted course then we can claim that the given set of courses can not be completed. Otherwise a way to complete all the courses will always exist.

Time Complexity:

O(n + m).

For creating the list of dependents: O(m).

For initializing the indegree array: O(m).

For running the Kahn’s algorithm: O(n + m).

So total time complexity: O(n + m).

Auxiliary Space Used:

O(n + m).

For storing the list of dependents: O(m).

For the queue: O(n).

For the indegree array: O(n)

So, total auxiliary space used: O(n + m).

Space Complexity:

O(n + m).

Space used for input: O(m).

Space used for output: O(1).

Auxiliary space used: O(n + m).

So total space complexity: O(n + m).