| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3582 |
| 5 | strapple | 3515 |
| 6 | tourist | 3473 |
| 7 | Radewoosh | 3418 |
| 8 | Um_nik | 3376 |
| 9 | potato167 | 3368 |
| 10 | maroonrk | 3361 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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.
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?
It's adjacency one-linked lists.
head[v]is id of the first edge adjacent tov,next[e]is id of next edge. Look atforindfs— it should make sense.thank you for replying , what is the advantages for this way that cannot adjacency list do?
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.
Also note that you can store an arbitrary graph in this way, not only a tree.
I've seen this way in many tree problems so I thought it's for trees. thank you.
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 compilersvectorreserves double of necessary memory, on another — only 1.5 times).in C++, I can build adjecency list without vector and with no extra momery thank you anyway.
It IS adjacency lists. Look at this code.