#include <map>
template<Vertex>
class BfsVisitor {
public:
void ExamineVertex(const Vertex& vertex) {
current_vertex_ = vertex;
}
void DiscoverVertex(const Vertex& vertex) {
if (!root_is_found_) {
root_is_found_ = true;
current_vertex_ = vertex;
}
parent_[vertex] = current_vertex_;
}
size_t DistanceTo(const Vertex& target) const {
size_t counter = 0;
Vertex current_target = target;
while (true) {
Vertex parent_of_target = parent_[current_target];
if (parent_of_target == current_target) {
return counter;
} else {
++counter;
current_target = parent_of_target;
}
}
}
Vertex Parent(const Vertex& vertex) const {
return parent_[vertex];
}
private:
map<Vertex, Vertex> parent_;
Vertex current_vertex_;
bool root_is_found_ = false;
}