Здравствуйте codeforces-чане!!!
у меня такая проблема я хочу найти все пути между вершинами 1 и n
дайте подсказку уже намучился :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | atcoder_official | 149 |
6 | -is-this-fft- | 148 |
6 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
10 | cry | 143 |
Здравствуйте codeforces-чане!!!
у меня такая проблема я хочу найти все пути между вершинами 1 и n
дайте подсказку уже намучился :)
Название |
---|
Встречный вопрос
тебе нужно найти все пути например -> 1--2--3--..--N-1--N или все длины путей из 1 в N?
Рассмотрим случай полного n-вершинного графа (любые две вершины соединены ребром). Тогда количество путей межу двумя выбранными вершинами составит 1+C(1,n — 2) + C(2, n — 2) + ... C(n — 2, n — 2) = 2^ (n — 2), т.е. количество таких путей имеет экспоненциальный порядок роста. Для достаточно больших n вы за разумное время все эти пути даже вывести на экран не сможете. Вы точно уверены, что нужно решить именно такую задачу? :)
Их на самом деле будет чуть больше, потому что каждую Сшку нужно умножить на факториал и получить Aшку, ведь после того, как мы выбрали промежуточные, мы можем их переставить как хотим.
Практически так, это будет A(n-2,0) + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2).
Просто dfs примерно вот такой:
Стандартным ДФС'ом совсем в тупую не решить, Ваш пример еще и зациклится.
Конечно, если в графе есть циклы, то он зациклится. Если условие задачи будет более конкретным, можно добавить некоторые условия в dfs.
Но если так подумать, то в данной задаче не говорится про ограничение длины пути. Так что может быть такое, что путь может зациклиться, пройтись 1, 2, 3 ... раз(а) по циклу. Тогда будет вообще бесконечность путей.