Codeforces Round #743 (Div. 2) , Help in topological sorting Q

1

Yesterday 's contest had some very good problems , unfortunately, it became unrated.
Problem Link :Problem - C - Codeforces

The problem is based on standard topological sort Prerequisite problem .
I am stuck somewhere .
If the cycle was found in the graph I printed -1 as the answer.
else
I found the topical sort of all the chapters , using cycle detection + DFS + queue.

After finding the topological ordering (stored in a queue) of chapters how do I count the number of times I will have to read the book/number of passes required???

Please help !!!

2

I don’t think the problem is exactly related to topological sorting, like yes it was but with a little variation.
Solution Link
I have used the logic of Khan’s Algorithm, with a little variation using set. If you’re able to know why I have used the set here, then awesome…you got the question.
Note that, whenever the inner while loop terminates, we need to increment our answer by 1.

1 Like
3

If you want to see solution related to variation of topological sort then check this out
Solution
P.S: This is not my solution.

1 Like
4

Thanks, I will see