| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 158 |
| 5 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | djm03178 | 155 |
| 9 | TheScrasse | 154 |
| 10 | Dominater069 | 153 |
Hi all.
I've came across this way of storing edges in many codes:
void addEdge(int u, int v) {
head[edges] = v;
prev[edges] = last[u];
last[u] = edges++;
}
How does it work? Why is it used over the 'traditional' array of vectors?
I appreciate your help!
Its basically the same. It's used because the array of vectors is slower. Personally I have never used it because I find it "ugly" and have never had problem with TL because of graph representation.
Good day to you.
You basically have array of edges, where each edge has "pointer" to parent (i.e. previous edge FROM same node) {you might also want TARGET {head in your code} node + PRICE + anything else you want}. You also have to keep (last array) an array with a "pointer" to "TOP" edge from each node.
So basically when you want to iterate over all edges FROM a node, you take look to the "LAST" array and keep iterating over the "pointers" {PREV in your code}.
It might be harder to understand + to operate with. Yet, it is slightly faster + it can be used in languages with no "vector"-like structure .
The memory cost is O(N+M) with no other overhead, which is also nice.
Good Luck!
Well, this way of has its pros and cons... I prefer to use it only when solving flow problems. For example, you may want to find quickly the edge, which goes in the opposite direction. If you add edges in pairs, the opposite of E is E^1.
Could you please give a link to a full solution with this representation ?
Here you go: link.