kingofnumbers's blog

a way to store a tree
By kingofnumbers, 11 years ago, In English

Hi when I was trying to understand the solution for 293E - Close Vertices 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.

can you tell about this way to store the tree.

thanks for helping.

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for replying , what is the advantages for this way that cannot adjacency list do?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Also note that you can store an arbitrary graph in this way, not only a tree.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've seen this way in many tree problems so I thought it's for trees. thank you.

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        in C++, I can build adjecency list without vector and with no extra momery thank you anyway.

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It IS adjacency lists. Look at this code.

      → Reply