#include<vector>
#include<deque>

struct BreadthFirstSearchGraph {
    struct Node {
        std::vector<Node*> arc;
        bool explored = false;
        int dist;
    };
    std::deque<Node> nodes;  // We use deque instead of vector so that pointers in `arc` don't get invalidated due to
                             // reallocation when capacity gets exceeded
    
    Node* add_node() {
        nodes.push_back(Node());
        return &nodes.back();
    }
    void add_edge(Node* u, Node* v) {
        u->arc.push_back(v);
    }
    void breadth_first_search(Node* start) {
        std::deque<Node*> queue(1, start);
        start->explored = true;
        start->dist = 0;
        
        while(queue.size() > 0) {
            Node* cur = queue.front();
            queue.pop_front();
            
            for(Node* next : cur->arc) {
                if(!next->explored) {
                    next->explored = true;  // Handle exploration tagging on adding to queue, to optimize queue size
                                            // a bit by preventing a node from being added repeatedly 
                    next->dist = cur->dist + 1;
                    queue.push_back(next);
                }
            }
        }
    }
};

int main() {
    BreadthFirstSearchGraph graph;
    
    graph.add_node();
    graph.add_node();
    graph.add_edge(&graph.nodes[0], &graph.nodes[1]);
    // ...
    // Populate the graph with add_node and add_edge
    
    graph.breadth_first_search(&graph.nodes[0]); // Assumes node 0 is where we start the search
}