e-olymp 209. Защита от копирования

Задача

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.
Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

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

На первой строке два числа $N (N ≤ 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

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

Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 5
1 2
2 3
3 5
5 2
2 4
1
2 12 20
1 2
2 3
3 4
4 5
5 6
6 1
7 8
8 9
9 10
10 11
11 12
12 7
6 3
1 4
2 5
12 9
7 10
8 11
6 12
3 9
2

Код программы

Решение задачи

С помощью векторов будем запоминать связи между смешариками, где смешарики — это вершины. Две вершины будут смежными, если смешарики дружат между собой. Будем использовать обход в глубину. Для решения задачи воспользуемся алгоритмом Форда-Фалкерсона, чтобы найти максимальный поток. Будем искать максимальный поток от одной вершины до каждой. Из всех найденных максимальных потоков выбираем минимальный — это и будет ответом на задачу.

Ссылки

e-olymp 4852. Кратчайшее расстояние

Задача взята с сайта e-olymp.

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

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

1

3 3

0 1 1

1 0 1

1 0 0

1 2 0

2

6 5

0 1 1 0 0 0

1 0 0 0 0 0

1 1 0 0 0 0

0 0 0 0 1 0

0 0 1 1 0 0

0 1 0 0 0 0

2 2 1 1 0 -1

3

3 1

0 0 0

0 0 1

1 1 0

0 -1 -1

Код

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве  graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q  будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

e-olymp 5338. Полный граф — 2

Задача

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке $[i, j]$ таблицы стоит «1», если граф может получить из фигурки $i$ фигурку $j$ одним сгибом. Иначе там стоит «0». Изначально в руках у графа Дуку чистый лист, то есть фигурка номер $x$ по его системе, сложить же он желает журавлика – фигурку номер $y$.
Найдите, за сколько операций граф достигнет желаемого.

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

В первой строке находится число $n (1 \leq n \leq 1000)$. В следующих $n$ строках задана таблица Дуку. В $(n + 1)$ — ой строке стоят числа $x$ и $y$.

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

Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите «-1».

Тесты

Ввод Вывод
1 4
0 0 1 0
0 0 0 1
1 0 0 1
0 1 1 0
1 2
3
2 4
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
1 2
-1
3 5
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 0 1
1 5
4
4 2
0 1
1 0
2 1
1
5 6
0 1 1 1 0 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
5 2
-1

Код

Решение

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

Ссылки

Условие задачи на e-olymp
Код на Ideone
Описание алгоритма на сайте e-maxx.ru

e-olymp 45. Топливо

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

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

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

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

Единственное число — искомое время.

Тесты

5   5   4   6
5  4  8  1  6
1  2  3
2  3  5
2  4  2
3  4  6
3  5  4
102
8 10 8 10
8 11 8 0 8 12 8 12
7 8 2
7 6 4
6 2 3
2 1 4
2 3 1
3 1 2
1 5 9
3 5 6
3 4 5
4 5 2
690
11 10 9 5
9 9 9 9 4 9 12 10 10 9 13
3 1 9
1 2 5
2 8 6
2 7 4
1 4 8
4 5 4
4 6 8
1 9 6
9 10 3
10 11 3
520
2 1 3 1
0 6
1 2 10
30
50 50 43 50
44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
40 41 1
41 42 1
42 43 1
43 44 1
44 45 1
45 46 1
46 44 1
46 48 1
48 49 1
49 50 1
50 1 1
8400
3 3 1 2
3 0 1
1 3 1
2 3 2
1 2 4
6

Решение 1

Решение 2

 Объяснение 1

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

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто  оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp 

ideone(1)

ideone(2)

e-olymp 4853. Кратчайший путь

Задача

Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$

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

В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты

Входные данные Выходные данные
$4\;5$
$1\;4$
$1\;3$
$3\;2$
$2\;4$
$2\;1$
$2\;3$
$2$
$1\;2\;4$
$5\;4$
$2\;4$
$1\;2$
$2\;3$
$2\;5$
$5\;3$
$-1$
$4\;4$
$2\;3$
$2\;1$
$2\;4$
$4\;3$
$1\;3$
$2$
$2\;1\;3$
$6\;4$
$1\;6$
$1\;2$
$2\;4$
$5\;3$
$4\;5$
$-1$

Код программы

Решение задачи

Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 4000. Обход в глубину

Задача

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

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

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите искомое количество вершин.

Тесты

Входные данные Выходные данные
3 1
0 0 1
0 0 0
1 0 0
2
4 2
0 1 0 0
1 0 0 1
0 0 0 1
0 1 1 0
4
6 2
0 1 0 0 0 1
1 0 0 0 0 1
0 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
1 1 0 0 0 0
3
4 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
5 3
0 1 0 0 1
1 0 1 0 1
0 1 0 1 0
0 0 1 0 1
1 1 0 1 0
5

Код программы

Решение задачи

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 209. Защита от копирования

Условие

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.

Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

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

На первой строке два числа $N$ $(N \le 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

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

Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.

Тесты

Ввод Вывод
$5$ $5$
$1$ $2$
$3$ $2$
$2$ $4$
$3$ $5$
$2$ $5$
$1$
$5$ $5$
$1$ $3$
$3$ $5$
$5$ $2$
$2$ $4$
$4$ $1$
$2$
$2$ $1$
$2$ $1$
$1$

Код

Решение

Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.

Ссылки

Условие на e-olymp.com
Код на ideone.com

e-olymp 610. Древняя рукопись

Задача

В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно было не менее трех. С течением времени у них появились дети и разбрелись они по миру, причем как и их родители, каждый построил свой город. Опять же с течением времени количество родственников начало стремительно возрастать и решили они между некоторыми городами построить дороги, а некоторые из них, уже до этого успели построить и объездные дороги вокруг своего города. В рукописях упоминается, что количество городов в той стране не превышало $8000$. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра $1$ указывала на наличие дороги между городами, или вокруг города, или $0$ в случае отсутствия таковой.

Изучите древние рукописи и дайте ответ на вопрос: а сколько же дорог было построено между городами?

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

В первой строке задано количество городов $n$, а в последующих $n$ строках через пробел задано по $n$ чисел, которые указывают на наличие или отсутствие соответствующей дороги.

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

Количество построенных между городами дорог.

Тесты

Входные данные Выходные данные
5
1 1 1 1 0
1 0 1 0 1
1 1 1 0 1
1 0 0 0 1
0 1 1 1 1
7
4
0 1 0 1
1 1 0 1
0 0 1 0
1 1 0 0
3
3
1 1 0
1 0 1
0 1 0
2
3
0 1 1
1 0 1
1 1 0
3
3
1 0 0
0 1 0
0 0 1
0

Код программы

Решение задачи

Задача не сложная – посчитать количество ребер в графе, заданном матрицей смежности.

Сложность задачи состоит в ограничениях по времени – не более одной секунды (ощутимо при больших значенях $n$, так как $3 ≤ n ≤ 8000$). Поэтому приходится быстро вводить данные в больших количествах. Для этого используем символьный массив и любую функцию, которая читает целую строку чисел (в моем случае – fgets()), которая читает строку, пока не встретит символ перевода строки – '\n'.

Далее по одному переводим символы в числа и суммируем их в переменной k, после чего выводим.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 93. Truck driving

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer, $C$ $(2 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input Output
$2$
$2$
$0$ $0$
$3$ $4$
$3$
$17$ $4$
$19$ $4$
$18$ $5$
$5.000$
$1.414$
$1$
$3$
$4$ $5$
$4$ $6$
$4$ $7$
$1.000$
$2$
$4$
$0$ $1$
$0$ $-1$
$1$ $0$
$-1$ $0$
$3$
$8$ $9$
$0$ $1$
$14$ $14$
$1.414$
$11.314$
$3$
$2$
$1$ $1$
$1$ $2$
$5$
$8$ $6$
$3$ $3$
$4$ $1$
$7$ $7$
$5$ $0$
$3$
$1$ $1$
$1$ $3$
$2$ $5$
$1.000$
$5.657$
$2.000$

Code

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $A$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

References

The task at E-Olymp
My solution at ideone

e-olymp 88. Месть Ли Чака

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

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

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

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

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные Выходные данные
$531$ $348$ $1645$ $911$
$1784353$ $453345$ $463973$ $214457$
$39252362$ $345673$ $786536$ $302328$
$68790234$ $679643$ $789057$ $281232$
$324$ $8564$ $45074547$ $32984424$

Код программы

Решение задачи

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 1868. Функция

Условие задачи
Вычислите функцию:

[latex]f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}[/latex]

Входные данные
Одно натуральное число [latex] n \; [/latex] [latex](1 \leq n \leq 10^{12}) [/latex].

Выходные данные
Значение [latex] f(n) [/latex], взятое по модулю [latex] 2^{32} [/latex].
Continue reading

A1038. Дейкстра?

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка  [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

  1. Для 1-го города найти кратчайшие маршруты в остальные города.
  2. В предположении, что каждый город соединен напрямую с каждым, найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города.

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

4
-1 2 4 -1
2 -1 1 6
4 1 -1 1
-1 6 1 -1

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

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).

e-olymp 1947. Конденсация графа

Условие задачи:

Для заданного ориентированного графа найти количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G’, вершинами которого служат компоненты сильной связности G, а дуга в G’ присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

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

Первая строка содержит два натуральных числа n и m (n10000, m100000) — количество вершин и ребер графа соответственно. Каждая из следующих m строк содержит описание ребра графа. Ребро номер i описывается двумя натуральными числами [latex]b_{i}[/latex], [latex]e_{i}[/latex](1 ≤ [latex]b_{i}[/latex], [latex]e_{i}[/latex] ≤ n) — номерами начальной и конечной вершины соответственно. В графе могут присутствовать кратные ребра и петли.

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

Количество ребер в конденсации графа.

Тесты:

Входные данные Выходные данные
4 4 2
2 1
3 2
2 3
4 3
6 9 1
1 2
2 4
4 1
4 2
3 2
2 6
3 5
5 3
6 2

Описание решения задачи:

Компонентой сильной связности называется такое подмножество вершин C, что любые две вершины этого подмножества достижимы друг из друга. Отсюда следует, что конденсация это граф, получаемый из исходного графа сжатием каждой компоненты сильной связности в одну вершину. Отсюда имеем структуру [latex]vertex[/latex]. Основным фундаментом данного алгоритма является следующая теорема: Пусть [latex]C[/latex] и [latex]{C}'[/latex] — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро ([latex]C[/latex],[latex]C'[/latex]). Тогда время выхода из [latex]C[/latex] будет больше, чем время выхода из [latex]{C}'[/latex]. Базируясь на этом, выполним серию обходов в глубину с помощью функции [latex]dfs[/latex] _ [latex]g[/latex], посещая весь граф. С визитом всех вершин графа,запоминаем для каждой время выхода, записывая это в созданный [latex]list[/latex]. Далее строится транспонированный граф. Запускаем серию обходов в глубину(функция [latex]dfs[/latex] _ [latex]tg[/latex]) этого графа в порядке, определяемом списком [latex]list[/latex] (а именно, в обратном порядке, т.е. в порядке уменьшения времени выхода). Каждое множество вершин, достигнутое в результате рекурсивного запуска обхода, и будет очередной компонентой сильной связности. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет, для этого зададим в структуре параметр [latex]colour[/latex]. Число цветов окраски будет равно количеству компонент сильной связности. Далее перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ([latex]a[/latex], [latex]b[/latex]), для которого [latex]components[a].colour[/latex] [latex]≠[/latex] [latex]components[b].colour[/latex], занесем во множество [latex]ribs[/latex] данную пару. Количество элементов во множестве [latex]ribs[/latex] будет равняться числу ребер в конденсации графа.

Условие задачи
Код задачи на с++
Засчитанное решение на e-olymp

e-olimp 4852. Кратчайшее расстояние

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex]  [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты 

 Входные данные  Выходные данные
3 1
0 1 0
0 0 0
0 0 0
 0 1 -1
6 5
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 1 1 0 0
0 1 0 0 0 0
2 2 1 1 0 -1
3 1
0 1 0
1 0 1
0 1 0
0 1 2

 

Реализация

Засчитанное решение на e-olimp.com

Код на ideone.com

Решение

Для решения данной задачи необходимо применить  алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем  вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид  [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

e-olymp 1108. Червячные дыры

Условие:

В 2163 году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:

  • Червячные дыры являются односторонними.
  • Время путешествия по любому тоннелю равно нулю.
  • Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
  • Звездная система в своих границах может иметь несколько концов червячных дыр.
  • По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
  • Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
  • Оба конца червячной дыры не могут находиться в одной звездной системе.
  • Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на 15 лет в будущее, а другая на 42 года в прошлое.

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

Ученый хочет достигнуть цикла червячных дыр, который поможет ему попасть в прошлое. Двигаясь по этому циклу несколько раз, можно прийти ко времени, когда имел место Большой Взрыв и наблюдать его собственными глазами. Напишите программу, которая определяет существование такого цикла.

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

Первая строка содержит количество звездных систем n (1n1000) и количество червячных дыр m (0m2000). Звездные системы пронумерованы от 0 (наша солнечная система) до n1. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа x, y и t. Эти числа указывают на возможность передвижения из звездной системы с номером x в звездную систему с номером y, при этом время изменяется на t (-1000t1000) лет.

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

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible«.

Тесты:

Входные данные Выходные данные
3 3
0 1 1000
1 2 15
2 1 -42
possible
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
not possible
3 3
0 1 -100
1 2 1
2 1 0
not possible

Решение:

Описание решения:

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана. Создадим вектор на [latex]n[/latex] элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью [latex]n[/latex] элементов нет отрицательных циклов, то после [latex]n-1[/latex] прохождения, изменения в массива кратчайших расстояний не будет. Поэтому, будем выполнять следующее [latex]n[/latex] раз:

  1. Возьмем первое ребро из вектора [latex]canals[/latex], и проведем сравнение: если исходная длина пути конца данного ребра из исходного вектора [latex]distance[/latex] больше, чем сумма длины пути начала вектора и стоимости прохода по данному ребру [latex]canals[].t[/latex], то изменим в векторе [latex]distance[/latex] элемент с номером конца исходного ребра, и изменим индикатор изменений [latex]x[/latex], чтобы показать, что в ходе данного прохода были внесены изменения.
  2. Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная [latex]x[/latex], то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

e-olymp 1948. Топологическая сортировка

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

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

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

Входные данные Выходные данные
6 6
1 2
3 2
4 2
2 5
6 5
4 6
4 6 3 1 2 5
2 2
1 2
2 1
-1
4 5
1 2
1 3
3 4
2 4
1 4
1 3 2 4
4 5
1 2
1 3
3 4
2 4
4 1
-1

Решение:

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

и

После выполнения этих функций был получен топологически отсортированный список вершин, но в обратном порядке. Поэтому разворачиваем его с помощью функции [latex]reverse[/latex] .

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

e-olymp 2267. Journey

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.
Maps
Help Ivan to find the longest possible route to the Domnino village.

Input

The first line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the first one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex] lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

Input Output
1 5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
-1
2 3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target.  (Function   void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ).  We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed.  Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function  void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic.  (Function  bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function  int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

Links

e-olymp 2401. Обход в ширину

Задача 2401

Условие

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.

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

В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].

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

Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].

Тесты

Входные данные Выходные данные
1 1 1 1
1
0
2 3 1 3
0 1 0
1 0 0
0 0 0
0
3 4 4 3

0 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

2
4 5 1 4
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
2

 

Решение

Для решения данной задачи необходимо использовать алгоритм «Поиск  в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь

Ссылки

Код программы на ideone.com

Условие задачи

Решенная задача

e-olymp 974. Флойд-1

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

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

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

 

Сам алгоритм хорошо описан на wikipedia

А вот сам код

 

 

e-olymp 982. Связность

Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть в любую другую.

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

В первой строке заданы количество вершин [latex]n[/latex] и ребер [latex]m[/latex] в графе соответственно [latex](1 \leq n \leq 100, 1 \leq m \leq 10000)[/latex]. Каждая из следующих m строк содержит по два числа [latex]u_i[/latex] и [latex]v_i[/latex] [latex](1 \leq u_i, v_i \leq n);[/latex]  каждая такая строка означает, что в графе существует ребро между вершинами [latex]u_i[/latex] и [latex]v_i[/latex].

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Тесты, взятые с e-olymp.com

Test Input Output
1 3 2
1 2
3 2
YES
2 3 1
1 3
NO

Мои тесты

Test Input Output
1 4 2
1 2
3 4
NO
2 4 5
1 2
2 1
2 4
2 4
4 2
NO
3 5 4
1 2
5 1
3 5
4 3
YES

Код программы

Алгоритм

Чтобы установить, является ли граф связным, я использовала удобный для этого алгоритм поиска в ширину. Он заключается в следующем: начиная с какой-то вершины, мы поочередно просматриваем все вершины, соседние с ней. Каждую посещенную вершину мы помечаем маркером. Затем повторяем этот процесс для каждой из соседних вершин, и так далее. Поиск будет продолжаться, пока мы не обойдем все вершины, которые можно достигнуть из данной. Если после этого в графе осталась хотя бы одна не помеченная вершина, значит из нее нельзя попасть в помеченные, то есть граф не является связным. При этом неважно, с какой вершины мы будем начинать поиск, ведь нам нужно установить сам факт, связный граф или нет.

Код программы

Засчитанное решение на сайте e-olymp.com