Способы задания графа

10 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Транзитивность ориентированного графа#54191
Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.

Проверьте, что заданный ориентированный граф является транзитивным.

Входные данные
Сначала вводится число n ( 1≤n≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.
Способы задания графа
✓ 20✗ 34900средняяВойти и решать
Транзитивность неориентированного графа#54189
Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует, что вершины u и w соединены ребром.

Проверьте, что заданный неориентированный граф является транзитивным.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.
Способы задания графа
✓ 14✗ 511 000средняяВойти и решать
Проверка на наличие параллельных ребер, ориентированный вариант#54161

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


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

Сначала вводятся числа n ( 1≤n≤1001≤𝑛≤100 ) – количество вершин в графе и m ( 1≤m≤10,0001≤𝑚≤10,000 ) – количество ребер. Затем следует m пар чисел – ребра графа.


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

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

Способы задания графа
✓ 25✗ 119800средняяВойти и решать
Проверка на наличие параллельных ребер, неориентированный вариант#54159
Неориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.

Входные данные
Сначала вводятся  числа n ( 1≤n≤100) – количество вершин в графе и m ( 1≤m≤10,000 ) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф содержит параллельные ребра, и «NO» в противном случае.
Способы задания графа
✓ 32✗ 36800средняяВойти и решать
Мафия#49448
В городе Лост-Хевен произошла серия загадочных преступлений. Жители напуганы и не знают, кому можно доверять. Местный Шериф позвал на помощь знаменитого детектива Нормана, чтобы тот помог ему найти главаря мафии. 
Норман принялся за дело и опросил всех жителей города. В итоге он теперь знает, кто кого боится. 
Норман знает, что главным подозреваемым будет тот житель города, который удовлетворяет следующим условиям:
1) Подозреваемый никого не боится.
2) Все остальные жители боятся подозреваемого. 
3) Существует ровно один такой человек, который удовлетворяет первым двум условиям.
Вы - программист, который помогает Норману. Норман дал вам информацию в виде списка, кто кого боится.  Помогите Норману определить главного подозреваемого. 

Формат входных данных
В первой строке записано натуральное число N - количество жителей города Лост-Хевен (1 <= N <= 1000). Во второй строке содержится неотрицательное число K (0 <= K <= 104) - количество записей сделанных Норманом после опроса всех жителей города. В следующих K строках записано по два числа (ai, bi) - обозначающие то, что i-й житель a боится жителя b (1 <= ai, bi <= n, ai не равно bi, каждая пара (ai, bi) уникальна).

Формат выходных данных
Выведите номер подозреваемого. Если выявить подозреваемого не представляется возможным, то в ответе укажите число -1.
Способы задания графа
✓ 71✗ 40800средняяВойти и решать
Схема дорог#44035
Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город Ai и город Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.
  • Пусть di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города ai,1, ..., ai,di,перечисленных в порядке возрастания.
  • I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.

Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 105, 1 <= M <= 105). Далее следует M строк, каждая из которых содержит 2 числа Ai и Bi (1 <= Ai < Bi <= N, 1 <= i <= M).
Если i≠j, то (Ai, Bi)≠(Aj, Bj). Все числа целые.

Выходные данные
Выведите N строк по формату, описанному в условии задачи.
 
 
Примеры
№ Входные данные Выходные данные
1 6 6
3 6
1 3
5 6
2 5
1 2
1 6		 3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5
2 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5		 4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
Способы задания графа
✓ 15✗ 23900средняяВойти и решать
Издевательство#38632
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
 - Издевается! - подумал Борман.
 - Кольцевая! - догадался Штирлиц.

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

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

Входные данные
В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

Выходные данные
Требуется вывести три числа — номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.
Примеры
№ Входные данные Выходные данные
1 5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0		 1 2 5
Простые задачи на переборСпособы задания графа
✓ 33✗ 25800средняяВойти и решать
Метро#38191
Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа Pi — количество станций на этой линии (2≤Pi≤50) и Pi чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).
 
Примеры
№ Входные данные Выходные данные
1 5
2
4 1 2 3 4
2 5 3
3 1		 0
2 5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5		 2
3 10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8		 1
4 4
2
2 1 2
2 3 4
1 3		 -1
Способы задания графа
✓ 22✗ 2081 100средняяВойти и решать
Файловый менеджер#33310
Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.
 
В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:
 
можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;
 
можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;
 
можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.
 
Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.
 
Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.
 
Петя знает, что ему сначала придется редактировать файл с номером a1, затем с номером a2 и так далее, а последним — файл с номером ak. В последовательности a1, a2, ..., ak один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.
 
Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.
 
Входные данные
В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.
 
В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.
 
Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).
 
Последняя строка входных данных содержит k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a1, a2, ..., ak.
 
Выходные данные
Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:
 
первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a1;
 
второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a2;
 
…
 
k-ый блок информации описывает перемещение от файла с номером ak–1 к файлу с номером ak.
 
Каждый блок информации выглядит следующим образом.
 
В первой строке блока записывается число L — наименьшее количество нажатий клавиш, необходимое для перемещения от очередного файла последовательности к следующему.
 
Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:
 
если нажимается клавиша вниз, то в строке записывается слово down;
 
если нажимается клавиша вверх, то в строке записывается слово up;
 
если нажимается клавиша Alt, то в строке записывается слово Alt;
 
при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.
 
Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.
 
Ввод Вывод
6
a
b
c
d
e
f
4
4 3 1 6
2
Alt
d
1
up
2
Alt
a
1
up
Алгоритм ДейкстрыБыстрая сортировкаСпособы задания графа
✓ 2✗ 31 000средняяВойти и решать
Мишина машина (В', В)#23371
Миша путешествует по стране на автомобиле. В стране есть несколько городов, соединенных дорогами, на каждой дороге может быть некоторое число ям.
Мише очень нравится ездить по дорогам на которых много ям, -  он участвует в популярном телешоу "Неперсистентные машинки" и за каждую посещенную яму ему платят по одной монете.

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

Формат входных данных
В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 105 , 0<= m <= 105)
В следующих m строках содержится по три целых числа, разделенных пробелами номера, -  городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество ям на каждой дороге неотрицательное число не превосходящее 106.
 
Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.
 
Формат выходных данных
Выведите одно число максимальное количество монет которое Миша сможет получить.
 
Ввод Вывод
4 4
1 2 1
2 3 1
1 4 1
4 3 0		 3
4 2
1 3 5
2 4 4		 5
 
Замечание
Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.
Кратчайшие пути в графеОбход в ширинуСпособы задания графа
✓ 22✗ 49900средняяВойти и решать
Поделиться
Класснуть