|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 09-2. Получи дерево
(Разбор)
Существует огромное количество способов решить эту задачу. Опишем один их наиболее быстрых. Обойдем наш граф в ширину из произвольной вершины. Далее для каждой вершины, кроме начальной выведем последнее ребро в кратчайшем пути от начальной вершины до нее. Полученное дерево называется деревом обхода в ширину.