Задачи к занятию. Тема 1 Обход в глубину

• Название: Тема 1 Обход в глубину
• Дата: 03.03.2019
• Размер: 28.14 Kb.
• Имя файла: Задачи к занятию.docx
• Тип: Документы; #69473

Задачи к занятию 22.01.2019
Тема 1: Обход в глубину

1. 
   Дерево?
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта

Дан неориентированный граф. Необходимо определить, является ли он деревом. Напоминаем, что неориентированный граф называется деревом, если он является связным и не содержит циклов. (Если количество ребер на 1 меньше чем кол-во вершин, то все ОК)

Формат входных данных

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

Формат выходных данных

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

Примеры

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

6

0 1 1 0 0 0

1 0 1 0 0 0

1 1 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

0 0 0 0 0 0

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

NO

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

3

0 1 0

1 0 1

0 1 0

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

YES

2. 
   Компоненты связности
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти:

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

Формат входных данных

Во входном потоке записано два числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 100000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.

Формат выходных данных

В единственной строчке выходного потока выведите количество компонент связности.

Примеры

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

6 4

3 1

1 2

5 4

2 3

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

3

3. 
   Самая удаленная вершина
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
Дано дерево. Требуется найти самую удаленную вершину от данной.

Формат входных данных

В первой строке дано число n — количество вершин дерева и число k — номер вершины, для которой нужно найти самую удаленную от нее (1 ≤ k ≤ n ≤100). Далее в n строках дана матрица смежности дерева.

Формат выходных данных

Выведите номер самой удаленной вершины от данной. Если существует несколько решений, допускается вывести любое. Если самая удаленная вершина от вершины k — сама вершина k, то требуется вывести ее.

Примеры

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

4 2

0 1 0 1

1 0 1 0

0 1 0 0

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

4
Тема 2. Топологическая сортировка

1. 
   Свинки-копилки
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
У Васи есть Nсвинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

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

Формат входных данных

В первой строке содержится число N — количество свинок-копилок (1 ≤ N ≤ 100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Формат выходных данных

Выведите единственное число: минимальное количество копилок, которые необходимо разбить.
Примеры

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

4

2

1

2

4

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


B. Производство деталей //если будет время
Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

Формат входных данных

Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1,p2,...,pn, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. В i-й строке нет повторяющихся номеров деталей. Сумма всех чисел ki не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходных данных

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

Примеры

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

3

100 200 300

1 2

0

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

300 2

2 1

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

2

2 3

1 2

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

5 2

2 1

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

4

2 3 4 5

2 3 2

1 3

0

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

9 3

3 2 1

Тема 3. Обход в ширину

1. 
   Длина минимального пути
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
В неориентированном графе требуется найти длину минимального пути между двумя вершинами.

Формат входных данных

Первым на вход поступает число N — количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности («0» обозначает отсутствие ребра, «1» -–– наличие ребра). Далее задаются номера двух вершин —– начальной и конечной.

Формат выходных данных

Выведите L –– длину кратчайшего пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число «-1».

Примеры

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

5

0 1 0 0 1

1 0 1 0 0

0 1 0 0 0

0 0 0 0 0

1 0 0 0 0

3 5

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

3

2. 
   Путь в графе
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Формат входных данных

Первым на вход поступает число N — количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 — наличие ребра). Далее задаются номера двух вершин — начальной и конечной.

Формат выходных данных

Выведите сначала L — длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину. Если пути между вершинами не существует, то требуется вывести одно число — «-1».

Примеры

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

5

0 1 0 0 1

1 0 1 0 0

0 1 0 0 0

0 0 0 0 0

1 0 0 0 0

3 5

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

3

3 2 1 5

Тема 4. Алгоритм Дейкстры.

1. 
   Кратчайший путь
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

Формат входных данных

В первой строке содержатся три числа: N, S и F (1 ≤ N ≤ 100, 1 ≤ S, F ≤ N), где N — количество вершин графа, S — начальная вершина, а F — конечная. В следующих N строках вводится по N чисел, не превосходящих 100, — матрица смежности графа, где −1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

Формат выходных данных

Требуется вывести искомое расстояние или «-1», если пути между указанными вершинами не существует.

Примеры

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

3 2 1

0 1 1

4 0 1

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

3

2. 
   Портал
   

Имя входного файла

стандартный ввод

Имя выходного файла

стандартный вывод

Ограничение по времени

2 секунды

Ограничение по памяти

64 мегабайта
Родители подарили Андрюше на Новый Год замечательную компьютерную игру «Portal 2». Действие игры происходит на клетчатом поле, в некоторых клетках которого находятся стенки. За один ход игрок может перейти из клетки в любую другую, смежную с ней по стороне. Помимо этого, находясь в любой клетке, можно сделать два выстрела из пушки в двух из четырех направлениях, тогда на месте попадания первого выстрела в стену образуется портал, а на месте попадания второго выстрела — выход из портала. После этого можно войти в портал, и тут же оказаться в выходе.

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

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

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

Формат входных данных

В первой строке через пробел записаны два целых числа N и M — размеры поля (4 ≤ N, M ≤ 50).

Следующие N строк содержат по M символов каждая и описывают поле очередного уровня игры. Если j-тый символ i-той строки равен «#», то в ячейке поля с координатами (i,j) находится стенка, иначе ячейка свободна. Начальная позиция игрока обозначена буквой «S», клетка, до которой надо добраться — буквой «T».

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

Формат выходных данных

Выведите одно целое число — ответ на задачу.

Примеры

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

10 9

#########

#......T#

#.....###

#.....###

#.....###

#....S..#

#.......#

#.......#

#.......#

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

3