| Входной файл: | Стандартный вход | Ограничение времени: | 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.