Алгоритмы на графах

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

 

Входные данные: В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

 

Выходные данные: Если способ рассадить ОВП существует, то  выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

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

 

Формат входных данных
В первой строке содержится одно натуральное число N (N ≤ 100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

 

Формат выходных данных
Вывести "YES", если граф является деревом, и "NO" иначе.

Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го).

Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.

 

Входные данные
В первой строке задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель.

 

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

Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

 

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

 

Входные данные: В первой строке находятся два числа N и M - количество студентов и количество пар студентов, обменивающихся записками (1<=N<=100, 0<=M<=(N(N−1))/2. Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

Выходные данные: Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры

№	Входные данные	Выходные данные
1	3 2 1 2 2 3	YES
2	3 3 1 2 2 3 1 3	NO

Вам задан ориентированный граф с N вершинами и M ребрами (1<=N<=20000, 1<=M<=200000). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

 

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

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержит описание ребра — два целых числа из диапазона от 1 до N — номера начала и конца ребра.

 

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

На первой строке выведите число K — количество компонент сильной связности в заданном графе. На следующей строке выведите N чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Ввод	Вывод
10 19 1 4 7 8 5 10 8 9 9 6 2 6 6 2 3 8 9 2 7 2 9 7 4 5 3 6 7 3 6 7 10 8 10 1 2 9 2 7	2 1 2 2 1 1 2 2 2 2 1

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

 

Формат входных данных
В первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер. Далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).

 

Формат выходных данных
Выведите матрицу смежности заданного графа.

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

 

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – размер матрицы. Затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.

 

Формат выходных данных
Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

 

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – количество вершин графа. Затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.

 

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

В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

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

 

Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. 

 

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

 

Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 

 

В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры

№	Входные данные	Выходные данные
1	4 5  1 2  2 3  3 4  1 4  4 1	No

В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом! 

 

Формат файла входных данных: 

Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно. 

 

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

 

Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние. 

 

Формат файла выходных данных: 

Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
 

Ввод	Вывод
4 4  aaa bacc cqe de  1 4  4 2  4 3  3 2	1 4 3 2
3 3  fi bru a  1 2  2 3  3 1	-1

Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.

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

В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.

 

В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. 

Примеры

№	Входные данные	Выходные данные
1	3 100000 100000 -51 100  100000 100000 100000 -50  100000	YES

Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

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

Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).

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

Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

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

(с) Шалдин В., 2017г.

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

 

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

 

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

 

Во входных данных записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа K_i (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует K_i пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 10⁹). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

 

Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
 

В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500\). Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.

 

Программа получает на вход одно число n (2≤n≤13000).

 

Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном  графе.

Примеры

№	Входные данные	Выходные данные
1	2	117
2	3	-164

Дополните программу, чтобы она верно решала следующую задачу.

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

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

 

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

 

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
 

Примеры

№	Входные данные	Выходные данные
1	6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

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

 

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

 

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

 

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры

№	Входные данные	Выходные данные
1	6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

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

 

Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.

 

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

В первой строке находятся два числа N и M - количество зданий и количество улиц, соединяющих здания (1<=N<=100, 1<=M<= (N*(N−1))/2. В следующей строке находятся числа S и E -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в M строках расположены описания дорог: 3 целых числа sieipi - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (1<=s_i, e_i<=N, 0<=p_i<=100 , дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

 

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

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

Ввод	Вывод
3 3 1 3 1 2 20 1 3 50 2 3 20	0.36

 

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

 

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

 

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

В первой строке находятся два числа N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0<=M<= (N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа s_i, e_i, l_i - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=s_i, e_i<=N, 0<=l_i<=100, дороги двунаправленные).

 

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

Необходимо вывести одно число - искомое расстояние.

Ввод	Вывод
3 2 1 2 1 2 3 2	3
3 0	0