kaiyu's blog

By kaiyu, history, 4 weeks ago, In English

1573C - Book

My idea is to use topological sort using BFS and output the max level the BFS reaches.

During BFS, If the indegree of child becomes 0, and the child's node number is greater than the parent node number, i'll push it into the queue without changing the level because this chapter will be understood in the current iteration itself . If the child's node number is lesser, i'll increment the level and push it into the queue because this chapter will require one more iteration to understand.

This solution fails on some case. What's wrong in this solution?

Here is my submission : 129318461

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Here you have a test for which your code fails:
1
5
1 5
2 1 3
1 4
0
0

Answer is 3, your code outputs 2.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thank you so much! Genuinely

    Was looking for this corner case since hours :p