Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 21 22 23 24 25 26 27 >> Отображать по:
#1105
Игра с обменами
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).

Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.

Например, если N=5. Тогда изначально Васей выписана последовательность

1 2 3 4 5

Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.

Например, он может последовательно получить следующие последовательности:

2 1 3 4 5 (поменяв числа на 1 и 2 местах)

2 5 3 4 1 (поменяв числа на 2 и 5 местах)

5 2 3 4 1 (поменяв числа на 1 и 2 местах).

Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.

От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).

Напишите программу, которая поможет Пете справиться с этой задачей.

Входные данные

Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).

Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).

Выходные данные

В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).

В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.

Примеры
Входные данные
5
5 2 3 4 1
2
1 2
2 5
Выходные данные
YES
3
1 2
2 5
1 2
Входные данные
5
2 3 4 5 1
2
1 2
2 5
Выходные данные
NO
#1111
Обход в глубину
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача D ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Программа выводит номера посещенной вершины графа после вызова обхода в глубину. По результатам работы этой программы требуется восстановить граф и вывести его в виде списка ребер.

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования Паскале и Си.

Паскаль

Си

var

   a: array [1..maxn, 1..maxn] of boolean;

  visited: array [1..maxn] of boolean;

 

procedure dfs(v: integer);

var

   i: integer;

begin

   writeln(v);

   visited[v] := true;

   for i := 1 to n do begin

     if a[v][i] and not visited[i] then begin

       dfs(i);

       writeln(v);

     end;

   end;

end;

 

procedure graph_dfs;

var

   i: integer;

begin

   for i := 1 to n do

     if not visited[i] then

       dfs(i);

end;

int a[maxn + 1][maxn + 1];

int visited[maxn + 1];

 

void dfs(int v) {

   printf("%d\n", v);

   visited[v] = 1;

   for (int i = 1; i <= n; i++) {

     if ((a[v][i] != 0) && (visited[i] == 0)) {

       dfs(i);

       printf("%d\n", v);

     }

   }

}

 

void graph_dfs() {

   for (int i = 1; i <= n; i++) {

     if (visited[i] == 0) {

       dfs(i);

     }

  }

}

Петина программа хранит граф с использованием матрицы смежности в массиве a (вершины графа пронумерованы от 1 до n). В массиве visited помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру graph_dfs для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

Входные данные

Первая строка входного файла содержит два целых числа: n и l количество вершин в графе и количество чисел в выведенной последовательности (1 ≤ n ≤ 300, 1 ≤ l ≤ 2n − 1). Следующие l строк по одному числу вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

Выходные данные

На первой строке выходного файла выведите одно число m максимальное возможное количество ребер в графе.

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

Примеры
Входные данные
6 10
1
2
3
2
4
2
1
5
6
5
Выходные данные
6
1 2
1 3
1 4
2 3
2 4
5 6
#1135
Гипер-каналы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо найти кратчайший путь в невзвешенном графе. Вершины задаются парой чисел.

«Не плюй в телепорт: вылетит — не поймаешь!»

На зараженной радиацией планете некоторые точки соединены между собой гипер-каналами. Когда человек заходит в гипер-канал в одной точке, он мгновенно оказывается в другой. Все гипер-каналы двусторонние — то есть их можно использовать для перемещения в обоих направлениях (как из первой точки во вторую, так и из второй в первую).

К сожалению, гипер-каналы платные — каждый проход через гипер-канал стоит 10 у.е.

Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).

Напишите программу, которая определит, какой минимальной суммой у.е. должен располагать путешественник, чтобы добраться из одной точки в другую, не рискуя своим здоровьем.

Входные данные

Во входном файле записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0N500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.

Выходные данные

В выходной файл запишите одно число — минимальную сумму, которой должен располагать путешественник для достижения цели. Если, не рискуя здоровьем, он не сможет добраться до конечной точки, запишите в выходной файл число 171717 (столько стоит лечение лучевой болезни на этой планете).

Примеры
Входные данные
10 10
-10 -10
3
-10 -10 -10 -10
-10 -10 1 1
10 10 1 1
Выходные данные
20
#1190
Введите одностороннее движение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Тридевятом Царстве было N городов, некоторые из которых были соединены дорогами. К сожалению, в последнее время добраться из одного города в другой стало очень сложно из-за возникших автомобильных пробок. В целях борьбы с пробками было решено все дороги сделать односторонними, т.е. разрешить проезд по каждой дороге только в одном направлении. При этом требуется, чтобы по-прежнему можно было из любого города попасть в любой другой.

Входные данные

Во входном файле записано сначала число N — количество городов (1≤N≤1000). Затем записано число M — количество дорог (1≤M≤100000). Далее идет M пар чисел, задающих дороги (каждая дорога описывается номерами городов, которые она соединяет). Не бывает дорог из некоторого города в тот же город. Между двумя городами может быть несколько дорог. Гарантируется, что до введения одностороннего движения можно было попасть из любого города в любой другой.

Выходные данные

В выходной файл нужно выдать M пар чисел, соответствующих дорогам (дороги должны быть выданы в том же порядке, в котором они заданы во входном файле). Для каждой дороги сначала должен быть записан номер города, из которого по ней можно будет уехать после введения одностороннего движения, а затем — номер города, куда эта дорога ведет.

Если ввести одностороннее движение так, чтобы можно было из любого города попасть в любой другой, нельзя, выходной файл должен содержать одно число 0.

Примеры
Входные данные
4
6
1 2
1 2
2 3
2 4
4 3
1 4
Выходные данные
2 1
2 1
3 2
4 2
4 3
1 4
Входные данные
2
1
1 2
Выходные данные
0
#1203
Кенгуренок Лео
  
Страница: << 21 22 23 24 25 26 27 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест