Презентация "Алгоритмы на графах. Топологическая сортировка отсечением вершин" - скачать презентации по Информатике онлайн

Содержание слайда:

Содержание слайда: Нахождение компонент связности В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер неориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести единственное число — количество компонент связности графа. Ограничение по времени — 1 сек. Ограничение по памяти — 16 Мб.

Содержание слайда: Домашнее задание Сколько различных путей есть в дереве с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами и k компонентами связности? Написать программу, определяющую количество компонент связности, с использованием матрицы смежности. Написать программу, определяющую максимальный размер компоненты связности, с использованием списка смежности.

Содержание слайда: Топологическая сортировка Дан ориентированный ациклический граф.

Содержание слайда: Топологическая сортировка Почему это возможно?

Содержание слайда: Топологическая сортировка Как быстро определить вершины, в которые не входит ни одно ребро?

Содержание слайда: Топологическая сортировка массив order длины n, order[i] — присвоенный i-й вершине порядковый номер при топологической сортировке; currorder — текущий присваиваемый номер.

Содержание слайда: Топологическая сортировка В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести номера, которые приобретут вершины после топологической сортировки. i-е число означает номер, приобретённый i-й вершиной. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.

Содержание слайда: Топологическая сортировка В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output.txt вывести упорядоченные топологически номера вершин. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.

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

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

Содержание слайда: Домашнее задание

Содержание слайда: Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С., Абакумов К. В., Мухачёва М. А.) «Интернет-уинверситет информационных технологий» http://www.intuit.ru/department/algorithms/basicalgos/