Parallel Courses

Hard
0/120
Average time to solve is 30m
profile
Contributed by
23 upvotes
Asked in companies
GrofersNaehas Software India Pvt. Ltd.

Problem statement

You are given an integer N which denotes the number of courses numbered from 1 to N and a matrix ‘prerequisites’, in which each row contains exactly two integers ‘A’ and ‘B’ which represents the course ‘A’ has to be studied in some semester before studying course ‘B’.

You are supposed to find the minimum number of semesters required to study all the courses.

If it is impossible to study all the courses, then return -1.

Note : 
There is no limitation on taking the number of courses in a particular semester as long as all the prerequisites for taking the course are satisfied.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains two integers ‘N’ and ‘M,’ which denotes the number of courses and the number of rows of the matrix ‘prerequisites.’

The next M lines contain two integers, prerequisites[i][0] and prerequisites[i][1], denoting that prerequisites[i][0] has to be studied before prerequisites[i][1].
Output Format : 
For each test case, print the minimum number of semesters required to study all the courses.

Print the output of each test case in a separate line.
Constraints : 
1<= T <= 50
1 <= N <= 20000
0 <= M <= 20000
1 <= prerequisites[i][0], prerequisites[i][1] <= N
prerequisites[i][0] != prerequisites[i][1], for any valid i

Time Limit: 1 sec
Sample Input 1 :
2
7 6
1 6
2 6
3 6
4 6
5 6
6 7
5 5
1 2
2 3
3 4
4 5
5 1
Sample Output 1 :
3
-1
Explanation For Sample Input 1 :
In the first test case, there are seven courses and six prerequisites. 1, 2, 3, 4, and 5 should be finished before 6, and 6 should be finished before 7.
In the first semester, Courses to be taken - 1, 2, 3, 4, and 5. In the second semester, Courses to be taken - 6. In the third semester, courses to be taken - 7. If the courses are taken in this manner, then all the courses can be finished in three semesters.

In the second test case, there are five courses and five prerequisites. 1 should be finished before 2, 2 should be finished before 3, 3 should be finished before 4, 4 should be finished before 5, and 5 should be finished before 1. All the courses are dependent on other courses. There is no course to start in the first semester. So, none of the courses can be finished. So, the answer is -1.
Sample Input 2 :
2
7 7
1 6
2 6
3 6
4 6
5 6
6 7
7 1
5 4
1 2
2 3
3 4
4 5
Sample Output 2 :
-1
5
Hint

 Finding the in-degrees of all the vertices will be helpful. Isn’t it?

Approaches (1)
BFS + Topological Sorting

The idea is to represent the given prerequisites as a directed graph and then use topological sorting to find the minimum number of semesters.

To construct the graph, we can use an array of an unordered set of integers. The indexes will represent the course and the values in the unordered set will represent the courses for which the key is a prerequisite. After that, find the indegree of every vertex and will do a Breadth-first Search. Indegree of a vertex is the number of edges from any vertex to the given vertex. Whenever we visit a vertex, we will reduce the in-degree of all its connected vertices by 1. If the in-degree of a vertex becomes 0, it means that the vertex can be taken in the particular semester and all the prerequisites for this course are already satisfied. 

The steps are as follows:

  • Make a directed graph named ‘graph’ from the given matrix ‘prerequisites’ and count indegrees of all the vertices.
    • Declare an array of an unordered set of integers ‘graph’.
    • Iterate over all the tickets:
      • Let the first element of the current row be denoted by ‘a’ and the second element of the current row be denoted by ‘b’.
      • Append ‘b’ at the end of graph[a].
      • Increment the indegrees of b by 1.
  • Initialize two integers ‘numberOfSemesters’ and ‘coursesFinished’ to 0 which stores the number of semesters required to study all the courses and the number of courses finished till that iteration respectively.
  • Declare a queue for performing Breadth-first Search.
  • Iterate over all the vertices:
    • If the in-degree of a particular vertex is 0, then push it into the queue.
  • Execute a while loop with the condition size of the queue is greater than 0:
    • Iterate from 0 to the current size of the queue:
      • Pop the top vertex from the queue and increment ‘coursesFinished’ by 1.
      • Iterate over all the courses for which the top vertex is a prerequisite and decrement their indegrees by 1. If the in-degree of any of the vertices becomes equal to 0, push it into the queue as we can study this course in the next semester.
    • Increment the ‘numberOfSemesters’ by 1 as let (‘numberOfSemesters’ = k), it means on kth iteration, we are finding the courses to be taken in the kth semester.
  • If we can complete all the courses, ie. ‘coursesFinished’ becomes equal to the number of courses then return ‘numberOfSemesters’ as the final answer.
  • Otherwise, return -1.
Time Complexity

O(N + M), where N is the number of courses and M is the number of prerequisites.

 

As the time complexity of a Breadth-first Search is O(V+E), where V is the number of vertices and E is the number of edges. In our case, the number of vertices is equal to the number of courses and the number of edges is equal to the number of prerequisites. Hence, the overall time complexity is O(N + M).

Space Complexity

O(M), where M is the number of prerequisites.

 

We are constructing a graph using the matrix ‘prerequisites’ of size MX2 and storing all the elements less than or exactly once in the array of unordered sets. Hence, the overall space complexity is O(M).

Code Solution
(100% EXP penalty)
Parallel Courses
Full screen
Console