#include <cstddef>
#include <vector>
#include <map>
#include <utility>
template<class Vertex>
class BfsVisitor {
public:
void ExamineVertex(const Vertex &vertex) {
current_vertex = vertex;
}
void DiscoverVertex(const Vertex &vertex) {
if (current_vertex == -1) {
parents->insert(std::make_pair(vertex, vertex));
distance->insert(std::make_pair(vertex, 0));
} else {
parents->insert(std::make_pair(vertex, current_vertex));
distance->insert(std::make_pair
(vertex, distance->at(current_vertex) + 1));
}
}
size_t DistanceTo(const Vertex &target) const {
return distance->at(target);
}
Vertex Parent(const Vertex &vertex) const {
return parents->at(vertex);
}
private:
std::map<Vertex, int> *distance = new std::map<Vertex, int>;
std::map<Vertex, Vertex> *parents = new std::map<Vertex, Vertex>;;
Vertex current_vertex = -1;
};