Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 29 Mar, 2021

Hard

```
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.
```

```
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].
```

```
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.
```

```
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
```

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.

- Declare an array of an unordered set of integers
- 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.

- Pop the top vertex from the queue and increment
- 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.

Similar problems

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Valid Arrangement of Pairs

Hard

Posted: 28 Jan, 2022

Left Right Print

Moderate

Posted: 9 Jul, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

The Summit

Easy

Posted: 15 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022