Блог пользователя strglntoexist

Автор strglntoexist, история, 3 года назад, По-английски

Here is the link of the problem: 1547G - How Many Paths?

Here is the code which is getting TLE:

Code

I am using dfs to find cycle and the number of paths from 1 to the current vertex. This is dfs1 function. Then I am using these information to get the answer in dfs2 function. The cycle function is for getting the vertex which form the cycle. The cycle array marks the nodes of the cycle. The arr array is to count the number of paths or how many times each vertex is visited and the ans array is for storing the answer. The par array stores the parent of each vertex which is used to get the cycle in cycle function. The vis arrays are for detecting a cycle. But i am getting TLE. I have used dfs 2 times . As dfs is O(V+E) it should pass. Can anybody explain why I am getting TLE? Here is the submission: 122422271

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your code goes into TLE for the following test case :

1
6 6
1 5
3 6
5 1
5 3
6 3
6 5
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can see the tutorial.