Блог пользователя 123a

Автор 123a, 11 лет назад, По-русски

Здравствуйте codeforces-чане!!!

у меня такая проблема я хочу найти все пути между вершинами 1 и n

дайте подсказку уже намучился :)

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Встречный вопрос
тебе нужно найти все пути например -> 1--2--3--..--N-1--N или все длины путей из 1 в N?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Рассмотрим случай полного n-вершинного графа (любые две вершины соединены ребром). Тогда количество путей межу двумя выбранными вершинами составит 1+C(1,n — 2) + C(2, n — 2) + ... C(n — 2, n — 2) = 2^ (n — 2), т.е. количество таких путей имеет экспоненциальный порядок роста. Для достаточно больших n вы за разумное время все эти пути даже вывести на экран не сможете. Вы точно уверены, что нужно решить именно такую задачу? :)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Их на самом деле будет чуть больше, потому что каждую Сшку нужно умножить на факториал и получить Aшку, ведь после того, как мы выбрали промежуточные, мы можем их переставить как хотим.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Практически так, это будет A(n-2,0) + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2).

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Просто dfs примерно вот такой:

void dfs (v) {
 if (v == n) {
    output_path();
    return;
 }
 for (v,u) in E
   dfs (u);
}
  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Стандартным ДФС'ом совсем в тупую не решить, Ваш пример еще и зациклится.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Конечно, если в графе есть циклы, то он зациклится. Если условие задачи будет более конкретным, можно добавить некоторые условия в dfs.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Но если так подумать, то в данной задаче не говорится про ограничение длины пути. Так что может быть такое, что путь может зациклиться, пройтись 1, 2, 3 ... раз(а) по циклу. Тогда будет вообще бесконечность путей.