DFS using adjacency lists much slower than using a C++ vector?

Revision en1, by Hyeokshin, 2018-05-03 12:00:50

Trying to solve 862B about the maximum number of edges one can add to a certain tree so that it's still a bipartite graph. I went with the "let's code everything ourselves" approach and limited myself to C. Here's my code.

Code

I looked at others' submissions and they used similar approaches but almost all of them used the vector class in C++. My code works fine on most tests including ones with n = 100k, running them in <50 ms, but then there's a test where one node has loads of edges and it times out at >2000 ms. Why? Even if you use a vector, the amount of recursive calls should still be the same, which should be the limiting factor here in terms of speed, right? Do I have an infinite loop?

Tags dfs, vector, dfs and similar

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hyeokshin 2018-05-03 12:00:50 3042 Initial revision (published)