Step 1 of 6
Adjacency lists
A graph is a set of vertices (numbered 0..n-1 here) connected by edges. Road maps, social networks, build dependencies and network topologies are all graphs.
The standard representation is an adjacency list: for each vertex, the list of its neighbors.
std::vector<std::vector<int>> adj(n);
adj[a].push_back(b); // edge a -> b
adj[b].push_back(a); // ...and b -> a if the graph is undirected
It uses O(V + E) memory, far less than an n × n matrix for the sparse graphs you meet in practice.
Your turn: write build(n, edges, directed) returning the adjacency list, and int max_degree(const std::vector<std::vector<int>>& adj) returning the largest number of neighbors any vertex has.