Yesterday 's contest had some very good problems , unfortunately, it became unrated.
Problem Link : https://mirror.codeforces.com/contest/1573/problem/C
The problem is based on standard topological sort Prerequisite problem .
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 of chapters (stored in a queue a ->b->c->d.... )how do I count the number of times I will have to read the book/number of passes required ???
Please help !!!
you can use dp to find the answer.
let $$$dp[v]$$$ be the minimum number of times you need to read the book to understand chapter $$$v$$$.
the answer will be the maximum of $$$dp[v]$$$ for all $$$1 \leq v \leq n$$$.
let $$$f(u,v)$$$ be a function that is equal to 1 if $$$u > v$$$, and 0 otherwise.
then, $$$dp[v]$$$ will be the maximum of $$$dp[u] + f(u,v)$$$ over all children of $$$v$$$ like $$$u$$$.
129187840
hope it helps!