Варианты 31-40 (Сложность 4)
Создать класс неориентированного графа. Реализовать в этом классе функцию обхода всех вершин графа методом поиска в глубину с использованием рекурсии. Для хранения информации о вершинах и связях использовать список структур.
Создать класс неориентированного графа. Реализовать в этом классе функцию обхода всех вершин графа методом поиска в глубину без использования рекурсии. Для хранения информации о вершинах и связях использовать список структур.
Создать класс неориентированного графа. Реализовать в этом классе функцию обхода всех вершин графа методом поиска в ширину. Для хранения информации о вершинах и связях использовать список структур.
Создать класс неориентированного графа. Реализовать в этом классе функцию поиска эйлерова цикла методом поиска в глубину. Для хранения информации о вершинах и связях использовать список структур.
Создать класс неориентированного графа. Реализовать в этом классе функцию поиска гамильтонова цикла методом поиска в глубину. Для хранения информации о вершинах и связях использовать список структур.
…
…
…
…
…
Варианты 41-50 (Сложность 5)
Создать класс ориентированного графа и использовать его для решения следующей задачи. В некотором городе W узкие улицы, поэтому в городе организовано одностороннее движение. Но в связи с ремонтными работами по расширению дорог некоторые улицы перекрыты для проезда. На рисунке изображён пример расположения площадей и оставшихся улиц с указанным направлением движения.
Требуется найти количество областей, на которые стал разбит город - таких, что в каждой области с любой площади можно доехать до любой другой. В данном примере такими областями являются множества {1,2,3}, {4} и {5,7,6}, при этом ответ будет 3.
Входные данные: в первой строке количество площадей N (от 1 до 15) и количество дорог M. В каждой из следующих M строк записаны два числа ui и vi – начало и конец i-й дороги.
Выходные данные: количество областей, на которые разбит город.
-
Пример входных данных
Пример выходных данных
7 10
1 2
2 3
2 5
2 4
3 1
3 4
4 5
5 7
6 5
7 6
3
Создать класс неориентированного графа и использовать его для решения следующей задачи. N шестеренок пронумерованы числами от 1 до N (N<= 10). Задано M (0<=M<=45) соединений пар шестерен в виде (i,j), 1<=i<j<=N (шестерня с номером i находится в зацеплении с шестерней j). Необходимо определить, можно ли повернуть шестерню с номером 1? Если да, то найти количество шестерен, пришедших в движение. Если нет – выдать сообщение.
Создать класс неориентированного графа и использовать его для решения следующей задачи. Найти произвольное разбиение 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде должны быть студенты, обязательно знакомые друг с другом. Круг знакомств задается матрицей A размера 2020 с элементами
a[i,j]=1, если i студент знаком со студентом j;
a[i,j]=0, если i студент не знаком со студентом j.
Создать класс неориентированного графа и использовать его для решения следующей задачи. Имеется N человек и матрица А размера NN. Элемент a[i,j] равен 1, если человек i знаком с человеком j (a[i,j] =a[j,i]). Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди.
Создать класс неориентированного графа и использовать его для решения следующей задачи. На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомого).
Создать класс неориентированного графа и использовать его для решения следующей задачи. Сеть дорог определяется следующим образом. Имеется N перекрестков и K дорог, связывающих перекрестки. Каждая дорога определяется тройкой чисел: двумя номерами перекрестков и временем, требующимся на проезд по этой дороге. Найти кратчайший путь машины от перекрестка i до перекрестка j, если на перекрестке машина должна ждать время, равное числу пересекающихся дорог. Движение по дороге возможно в обоих направлениях.
Создать класс неориентированного графа и использовать его для решения следующей задачи. Пусть группа состоит из N человек. Назовем одного из этих людей знаменитостью, если он не знает никого из оставшихся, а его знают все. Задача состоит в том, чтобы в этой группе определить знаменитость (если она там есть). При этом разрешается задавать только вопросы вида "Извините, знаете ли Вы вон того человека?". (Предполагается, что все ответы правдивы, и что даже знаменитость ответит на поставленный ей вопрос). Найти минимально необходимое число вопросов, которое надо задать, и описать алгоритм опроса. Входные данные: матрица C[i,j], такая что C[i,j]=1, если i знает j, и C[i,j]=0 иначе.
Создать класс ориентированного графа и использовать его для решения следующей задачи. Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.
Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N(N<=50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.
Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, которая должна быть записана в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.
-
Пример входных данных
Пример выходных данных
3
2
1 2
2 3
1 3
3
1
2
3
…