Здравствуйте codeforces-чане!!!
у меня такая проблема я хочу найти все пути между вершинами 1 и n
дайте подсказку уже намучился :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
Здравствуйте 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 ... раз(а) по циклу. Тогда будет вообще бесконечность путей.