Презентация на тему Алгоритмы на графах. Топологическая сортировка поиском в глубину

мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных

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

n (1 ≤ n ≤ 10 000) — количество деталей двигателя. Вторая строка содержит

n натуральных чисел p1, p2, …, pn, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел ki не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей.
В первой строке выходного файла details.out должны содержаться два числа: минимальное время ( в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимы для этого производства. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором их следует производить для скорейшего производтсва детали с номером 1.
Ограничение по времени — 2 сек. Ограничение по памяти — 64 Мб.

глубину.
Используем поиск в глубину от всех вершин со входящей

степенью 0. Будем нумеровать вершины, из которых выходим, в обратном порядке.

При этом окажется, что граф отсортирован топологически.

которые были покинуты раньше, в вершины, которые были покинуты

позже.

Как это доказать?

Предположим, что это не так.
Пусть имеются вершины A и B, причём в процессе DFS вершина A была покинута раньше, чем вершина B. Пусть теперь существует ребро из A в B.

(но ещё не покинули B).
Два случая:
Покидаем A и

ещё не посещали B.
Покидаем A и посетили B.

Однако:
Из чёрной вершины в белую не бывает рёбер.
Есть серый путь из B в A, что с ребром из A в B даёт цикл, но граф ациклический.

вести себя алгоритм топологической сортировки отсечением вершин?
как будет вести

себя алгоритм топологической сортировки поиском в глубину?

ориентированном ациклическом графе с n вершинами?
Может ли быть так,

что правильным результатом топологической сортировки графа оказывается любой порядок его вершин?
Решить задачу о производстве деталей с помощью DFS.
Как использовать топологическую сортировку для определения наличия циклов в графе?