Help!!!Getting TLE on Test 2 of the problem G of CF Round 731 (Division 3)

Revision en5, by strglntoexist, 2021-07-14 11:51:32

The problem that I am getting TLE is problem G of CF Round 731 named How Many Paths? Here is the link: 1547G - How Many Paths? 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

Tags dfs, time limit exceeded, cycle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English strglntoexist 2021-07-14 12:02:47 119
en7 English strglntoexist 2021-07-14 11:55:45 1458 (published)
en6 English strglntoexist 2021-07-14 11:54:26 2068 (saved to drafts)
en5 English strglntoexist 2021-07-14 11:51:32 4 (published)
en4 English strglntoexist 2021-07-14 11:49:41 77
en3 English strglntoexist 2021-07-14 11:48:17 2103
en2 English strglntoexist 2021-07-14 11:40:20 4 Tiny change: 'r[400005];\nint ans[' -> 'r[400005];``\nint ans[' (saved to drafts)
en1 English strglntoexist 2021-07-14 11:38:20 2988 Initial revision (published)