Last Updated: 29 Mar, 2021
Parallel Courses
Hard
Asked in companies
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.
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
Approaches
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.
- Iterate from 0 to the current size of the queue:
- 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.