I was solving this problem on the CSES Problemset Longest Flight Route.
Here is my code
The code is getting Accepted in all but 2 testcases(TLE in those 2) .
I cannot debug with those testcases since they are HUGE.
I reckon that the problem is in my BFS Code but I can't seem to find why it would go in an infinity loop.
If anyone could provide a testcase or something it would be incredibly helpful.
Thanks.
Auto comment: topic has been updated by arnav2004 (previous revision, new revision, compare).
BFS only runs in $$$O(m)$$$ when you're looking for the shortest path. As an example of why your code is slow, it runs in $$$O(n^2)$$$ on the following test case:
2k+1 3k
1 3
1 2
2 3
3 4
3 5
4 5
...
2k-1 2k+1
2k-1 2k
2k 2k+1
Thanks a lot! That helped :)