3a51's blog

What is the difference between vector and chain forward star in 2110E
By 3a51, history, 16 months ago, In English

This problem need to calculate the Eulerian Path.

I used vector to store the graph as usual, but I got TLE on 21. 322076342

After I changed to chain forward star, It passed. 322077896

Does anybody know the reason? I think both methods are $$$O(n\log n)$$$.

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

»
16 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

That's because your first submission is $$$O(n^2)$$$, since in dfs, the variable $$$i$$$ does not change when dfs(x) is called again during the recursion of dfs(to). It should be changed every time to st[x] though. Here's a fixed version: 322083641.

In your second submission, since you have &i = st[x], then this issue does not happen.

→ Reply
»
16 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

The correct version is $$$O(n)$$$ though

→ Reply