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

What is the difference between vector and chain forward star in 2110E
Автор 3a51, история, 15 месяцев назад, По-английски

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)$$$.

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

»
15 месяцев назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
15 месяцев назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить