Объясните как реализовывать и пользоваться cписками смежности.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | adamant | 155 |
8 | nor | 154 |
9 | maroonrk | 152 |
10 | Dominater069 | 148 |
Объясните как реализовывать и пользоваться cписками смежности.
Название |
---|
В списках смежности используется 3 массива ls, r, prev.
В ls[v] хранится номер последнего ребра с которым связана вершина v, r[i] будет хранить номер вершины на которую ведет ребро i, prev[i] хранит номер ребра с которым вершина v была связана до ребра i.
Реализация:
m — кол-во ребер.
Если честно, то я так и не понял в чем суть. Список смежности — это структурка, где для каждой вершины храним в динамическом списке смежные вершины. В C++ делается через std::vector.
UPD:
Легче всего, мне кажется, так делается (на с++):
Получается, что graph[v] будет хранить список вершин связанных с вершиной v. Вот код:
И вот собственно dfs():
Мне кажется, или graph[v] будет хранить вектор векторов, а не список смежных вершин?
graph[][] сам по себе вектор векторов, а graph[v] -- это вектор (список вершин)
Я имею ввиду, что если объявлять:
То graph будет массивом, где в одной ячейке вектор векторов. graph получается трехмерным.
Да, это неверно. Нужно просто
или же
Да, точно! Просто я перепутал: вместо круглых скобок, написал квадратные)
моё http://codeforces.me/blog/entry/5195 подробное объяснение на эту тему, если есть вопросы — задавай!