**Editorialist :** Sudheera Y S

**Problem Link :** ZIO 2008 Problem 2

**Prerequisites :** Representation , Greedy

**Problem statement :**

There are some courses to be completed , and there are some prerequisites for some courses i.e you can take some course only after completing some other course . In one semester you can take as many courses as you want , but if you take some course , then that means that you have finished all the prerequisites of that course . Find the minimum number of semesters needed to complete all the courses satisfying the given condition.

**Idea :**

First , we will make a table which shows for any particular course which all courses are prerequisites for that particular course ( like an adjacency list ). Once we have the table , we will find the number of courses which don’t have any prerequisites and take all of them in the next semester and once we take that course , we will delete that course from the prerequisites of any other course if any ( so we will get to know which all courses we can do in the next semester ) .

**Subtask A :**

So first , let us make the table of the prerequisites .

In the first column we will have all the courses ( 10 in this case ) and in the second column we will have all the prerequisites of that course )

The initial would look something like this

1 | |
---|---|

2 | |

3 | |

4 | |

5 | |

6 | |

7 | |

8 | |

9 | |

10 |

So now let us fill the conditions one by one .

As we can see in the input , there are two types of given input :

- X before Y
- X after Y

Here is how we are going to fill the table for the given things.

- X is a prerequisite of Y , so in yth row we should add X to the prerequisite list ( 2nd column )
- Y is a prerequisite of X , so in xth row we should add Y to the prerequisite list ( 2nd column )

So now doing like this, let us take one by one and fill the table

- 4 before 5 → put 4 in 5th row 2nd column
- 2 after 5 → put 5 in the 2nd row 2nd column
- 4 before 2 → put 4 in the 2nd row 2nd column
- 6 after 7 → put 7 in the 6th row 2nd column
- 1 after 2 → put 2 in the 1st row 2nd column
- 2 before 3 → put 2 in the 3rd row 2nd column

.

.

.

So on ……

Now our final table looks like :

1 | 2,3,6 |
---|---|

2 | 5,4,7 |

3 | 2,4 |

4 | - |

5 | 4 |

6 | 7 |

7 | - |

8 | 1 |

9 | 10,8,1 |

10 | 2 |

Now here is our table .

Now let us start finding our answer .

4,7 Doesn’t have any prerequisite so we will do both of them in our first semester

1st Semester → 4,7

Now we can remove 4,7 from all the prerequisites ex . 5,6 …

And our table would look something like this :

1 | 2,3,6 |
---|---|

2 | 5 |

3 | 2 |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 1 |

9 | 10,8,1 |

10 | 2 |

Now in the second semester we can do all those which are not yet done and those which doesnt have any prerequisite .

In this case it is 5,6

Second semester → 5,6

Now as usual we will remove 5,6 from the prerequisite if any

Our table would look something like this :

1 | 2,3 |
---|---|

2 | - |

3 | 2 |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 1 |

9 | 10,8,1 |

10 | 2 |

Third semester → 2

We will remove 2 from all the prerequisite table and our new table would look something like this :

1 | 3 |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 1 |

9 | 10,8,1 |

10 | - |

Fourth semester → 3,10

We will remove 3 and 10 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 1 |

9 | 8,1 |

10 | - |

Fifth semester → 1

We will remove 1 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | 8 |

10 | - |

Sixth semester → 8

We will remove 8 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | - |

10 | - |

Seventh semester → 9

Now we see that we have completed all the courses and here we stop and we took seven semesters so our answer would be 7

**Answer : 7**

**Subtask B :**

There are total of 10 tasks so there would be 10 rows in our table and once we write all the prerequisites in the table , our table would look something like this :

1 | 8 |
---|---|

2 | 6,9 |

3 | 8,2,9 |

4 | 3,10,1,8 |

5 | 1 |

6 | - |

7 | 4,1 |

8 | 9 |

9 | 6 |

10 | 2 |

First semester → 6

We will remove 6 from all the prerequisite table and our new table would look something like this :

1 | 8 |
---|---|

2 | 9 |

3 | 8,2,9 |

4 | 3,10,1,8 |

5 | 1 |

6 | - |

7 | 4,1 |

8 | 9 |

9 | - |

10 | 2 |

Second semester → 9

We will remove 9 from all the prerequisite table and our new table would look something like this :

1 | 8 |
---|---|

2 | - |

3 | 8,2 |

4 | 3,10,1,8 |

5 | 1 |

6 | - |

7 | 4,1 |

8 | - |

9 | - |

10 | 2 |

Third semester → 8,2

We will remove 8 and 2 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | 3,10,1 |

5 | 1 |

6 | - |

7 | 4,1 |

8 | - |

9 | - |

10 | - |

Fourth semester → 10,3,1

We will remove 10,3 and 2 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | 4 |

8 | - |

9 | - |

10 | - |

Fifth semester → 5,4

We will remove 5 and 2 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | - |

10 | - |

Sixth semester → 7

Nowe we have completed all the courses and we took 6 semesters to complete it so our answer would be 6

**Answer : 6**

**Subtask C :**

We see that there are total of 10 courses so there would be 10 rows in our table and after filling the prerequisites , our table would look something like this :

1 | 2,7,8 |
---|---|

2 | 4 |

3 | 5 |

4 | 5 |

5 | - |

6 | 4 |

7 | 3 |

8 | 9 |

9 | 3 |

10 | 6,3,2 |

First semester → 5

We will remove 5 from all the prerequisite table and our new table would look something like this :

1 | 2,7,8 |
---|---|

2 | 4 |

3 | - |

4 | - |

5 | - |

6 | 4 |

7 | 3 |

8 | 9 |

9 | 3 |

10 | 6,3,2 |

Second semester → 3,4

We will remove 3 and 4 from all the prerequisite table and our new table would look something like this :

1 | 2,7,8 |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 9 |

9 | - |

10 | 6,2 |

Third semester → 6,7,2,9

We will remove 6,7,2 and 9 from all the prerequisite table and our new table would look something like this :

1 | 8 |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | - |

10 | - |

Fourth semester → 8,10

We will remove 8 and 10 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | - |

10 | - |

Fifth semester → 1

Now we see that all the courses are completed and we can stop here . We took 5 semesters to complete all the courses therefore the answer is 5

**Answer : 5**

**Subtask D :**

There are a total of 10 courses therefore the number of rows in our table would be 10 . After filling the table with the prerequisites our answer would look something like this :

1 | 2,4 |
---|---|

2 | 3 |

3 | 4,9 |

4 | - |

5 | 2 |

6 | 5,2 |

7 | 6 |

8 | 1,9,10,5 |

9 | - |

10 | 4,7 |

First semester → 4,9

We will remove 4 and 9 from all the prerequisite table and our new table would look something like this :

1 | 2 |
---|---|

2 | 3 |

3 | - |

4 | - |

5 | 2 |

6 | 5,2 |

7 | 6 |

8 | 1,10,5 |

9 | - |

10 | 7 |

Second semester → 3

We will remove 3 from all the prerequisite table and our new table would look something like this :

1 | 2 |
---|---|

2 | - |

3 | - |

4 | - |

5 | 2 |

6 | 5,2 |

7 | 6 |

8 | 1,10,5 |

9 | - |

10 | 7 |

Third semester → 2

We will remove 2 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | 2 |

7 | 6 |

8 | 1,10,5 |

9 | - |

10 | 7 |

Fourth semester → 1,5

We will remove 1 and 5 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | 6 |

8 | 10 |

9 | - |

10 | 7 |

Fifth semester → 6

We will remove 6 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 10 |

9 | - |

10 | 7 |

Sixth semester → 7

We will remove 7 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | 10 |

9 | - |

10 | - |

Seventh semester → 10

We will remove 10 from all the prerequisite table and our new table would look something like this :

1 | - |
---|---|

2 | - |

3 | - |

4 | - |

5 | - |

6 | - |

7 | - |

8 | - |

9 | - |

10 | - |

Eight semester → 8

Now we see that all the courses are completed and here we can stop and we took eight semesters to finish all the courses therefore our answer is 8

**Answer : 8**

Hope you understood