#include <map>
#include <memory>
template<class Vertex>
class BfsVisitor {
private:
std::shared_ptr<std::map<Vertex, Vertex>> graph {nullptr};
public:
BfsVisitor() {
graph.reset( new std::map<Vertex, Vertex>);
(*graph)[-1] = 0;
}
void ExamineVertex(const Vertex& vertex) {
(*graph)[-1] = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
(*graph)[vertex] = (*graph)[-1];
}
size_t DistanceTo(const Vertex& target) const {
Vertex box = target;
size_t length = 0;
while (true) {
if (box == 0 && (*graph).at(box) == 0) {
return length;
}
box = (*graph).at(box);
length++;
}
}
Vertex Parent(const Vertex& vertex) const {
return (*graph).at(vertex);
}
};