Задача B. Graph visitor

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:4000 Мб

Условие

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

template<Vertex>
class BfsVisitor {
public:
void ExamineVertex(const Vertex& vertex);
void DiscoverVertex(const Vertex& vertex);
size_t DistanceTo(const Vertex& target) const;
Vertex Parent(const Vertex& vertex) const;
}

Объект данного класса будет использован функцией обхода графа в ширину, аналогичной данной. Метод ExamineVertex будет вызван в момент извлечения вершины из очереди, метод DiscoverVertex будет вызван в момент добавления вершины в очередь.

После обхода графа визитор должен хранить кратчайшие расстояния от начальной вершины до всех остальных. Для получения расстояния до вершины будет использован метод DistanceTo.

Также, в процессе обхода в ширину визитор должен построить соответствующее такому обходу остовное дерево графа. Метод Parent будет использован для получения предка каждой вершины в таком графе. Родителем корневой вершины является она сама.

Экземпляр визитора передается в функцию по значению, и для эффективного копирования его размер должен быть не больше размера shared_ptr.

Материалы задачи

main.cpp

task.xml


0.047s 0.008s 17