#include <map>
#include <memory>
template<class Vertex>
class BfsVisitor {
public:
BfsVisitor() {
tree = std::make_shared<std::pair<Vertex, std::map<Vertex, Vertex>>>();
tree->first = 0;
}
void ExamineVertex(const Vertex& vertex) {
tree->first = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
tree->second[vertex] = tree->first;
}
size_t DistanceTo(const Vertex& target) const {
size_t dist = 0;
Vertex tmp = target;
while (true) {
if (tmp == 0 && tree->second.at(tmp) == 0) {
return dist;
}
dist++;
tmp = tree->second.at(tmp);
}
}
Vertex Parent(const Vertex& vertex) const {
return tree->second.at(vertex);
}
private:
std::shared_ptr<std::pair<Vertex, std::map<Vertex, Vertex>>> tree {nullptr};
};