strglntoexist's blog

By strglntoexist, history, 3 years ago, In English

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?

Full text and comments »

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