Презентация на тему "Алгоритмы на графах. Топологическая сортировка отсечением вершин" по информатике в формате powerpoint. Данная презентация для школьников 10-11 классов представляет собой "продвинутый" уровень изучения темы "Алгоритмов". Автор презентации: Югов Иван Олегович.
Фрагменты из презентации
Нахождение компонент связности
В первой строке файла input.txt заданы целые n и m — соответственно число вершин и число рёбер неориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами.
В файл output.txt вывести единственное число — количество компонент связности графа.
Ограничение по времени — 1 сек.
Ограничение по памяти — 16 Мб.
Топологическая сортировка
Топологической сортировкой называется присвоение номеров вершинам: любая дуга направлена из вершины с меньшим номером в вершину с бóльшим номером.
Почему это возможно?
Всегда найдётся вершина, в которую не входит ни одно ребро.
Такой вершине можно присвоить минимальное значение, после чего убрать её из графа.
