Здравствуйте codeforces-чане!!!
у меня такая проблема я хочу найти все пути между вершинами 1 и n
дайте подсказку уже намучился :)
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | adamant | 163 |
2 | awoo | 163 |
4 | TheScrasse | 157 |
5 | nor | 153 |
6 | maroonrk | 152 |
6 | -is-this-fft- | 152 |
8 | Petr | 145 |
9 | orz | 144 |
9 | pajenegod | 144 |
Здравствуйте 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 ... раз(а) по циклу. Тогда будет вообще бесконечность путей.