#include<vector>
#include<deque>
#include<algorithm>


struct DepthFirstSearchGraph {
    struct Node {
        std::vector<Node*> arc;
        bool explored = false;
    };
    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);
    }
    int depth_first_search(Node* cur, Node* prev = 0) {
        // Recursive depth first search that returns the max depth it reaches
        int max_depth = 0;
        cur->explored = true;
        for(Node* next : cur->arc) {
            if(!next->explored) {
                max_depth = std::max(max_depth, depth_first_search(next, cur)+1);
            }
        }
        return max_depth;
    }
};

int main() {
    DepthFirstSearchGraph 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
    
    int max_depth = graph.depth_first_search(&graph.nodes[0]); // Assumes node 0 is where we start the search
}