Why does push_back into vector<vector<int>> causing seg fault?

Question

Want to construct a Graph with adjacency list, but getting seg-fault when I add elements to vector<vector<int>>. adj.size() prints 5 which tells it has allocated memory, why the seg-fault in addEdge() method?

 #define V 5

    struct Edge {
        int src, dst;
    };

    void addEdge(vector<vector<int>> &adj, int u, int v)
    {
        adj[u].push_back(v);
    }

    void constructGraph(vector<vector<int>> &adj, vector<Edge> &edges)
    {

        for(Edge e : edges)
        {
            addEdge(adj, e.src, e.dst);
        }
    }

    int main()
    {
       vector<vector<int>> adj(V);

       vector<Edge> edges =
        {
            { 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
            { 3, 2 }, { 4, 5 }, { 5, 4 }
        };

        constructGraph(adj, edges);

       return 0;
    }

---

Answer 1

void addEdge(vector<vector<int>> &adj, int u, int v)

{
    adj[u].push_back(v);
}

is incorrect. The operator[]() for a vector ASSUMES the supplied index is valid. If u is not valid, the behaviour is undefined.

In your code, the vector passed has five elements, and the last edge in main()

vector<Edge> edges =

    {
        { 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
        { 3, 2 }, { 4, 5 }, { 5, 4 }               // note the last pair here
    };

will cause addEdge() to be called with u having a value of 5. That is one past the end.

While #define V 6 will fix the problem, it doesn't protect addEdge() from being passed a bad value of u. Instead I would implement addEdge() so it protects itself from bad data as follows.

void addEdge(vector<vector<int>> &adj, int u, int v)
{
    if (u < 0) return;                   // handle negative u
    if (u >= adj.size()) adj.resize(u+1);  //   resize if needed
    adj[u].push_back(v);
} 

An even better approach would be to avoid using supplied data - such as the data in edges in your main() - as array indices at all.