### kingofnumbers's blog

By kingofnumbers, 8 years ago,

Hi when I was trying to understand the solution for 293E - Близкие вершины by reading AC codes.

I was reading this code 3689358 , but I can't understand the way he stores the tree.

for me I usually use adjecency list to store graphs or trees.

thanks for helping.

edit: is it Euler tour? if yes how is way that the code build the Euler tour?

• -2

 » 8 years ago, # |   +13 It's adjacency one-linked lists. head[v] is id of the first edge adjacent to v, next[e] is id of next edge. Look at for in dfs — it should make sense.
•  » » 8 years ago, # ^ |   0 thank you for replying , what is the advantages for this way that cannot adjacency list do?
•  » » » 8 years ago, # ^ |   +5 It is just another way to store adjacency lists using a few pre-allocated arrays instead of dynamic-length arrays or lists. This way is a bit more compact, and perhaps a bit faster. On the other hand, it could lead to less intuitive code and more bugs as a result.
•  » » » 8 years ago, # ^ |   +6 Also note that you can store an arbitrary graph in this way, not only a tree.
•  » » » » 8 years ago, # ^ |   0 I've seen this way in many tree problems so I thought it's for trees. thank you.
•  » » » 8 years ago, # ^ |   +5 I think you're talking about storing list in vector, which can be significantly slower than arrays. So, the main advantage is performance. Also you can use this method for precise assessing of memory consumption (on some compilers vector reserves double of necessary memory, on another — only 1.5 times).
•  » » » » 8 years ago, # ^ |   0 in C++, I can build adjecency list without vector and with no extra momery thank you anyway.
•  » » » 8 years ago, # ^ |   0 It IS adjacency lists. Look at this code.