Adjacency List Architectures

Beyond Pointers

When you first learn about trees and graphs, you often start by defining a Node struct with pointers to its children or neighbors. This works fine for small problems. But in competitive programming, where the number of nodes N can reach a million, creating a million objects with new is a recipe for disaster. Each dynamic allocation is a slow system call, and the resulting nodes can be scattered all over memory, leading to poor cache locality and slow traversals. This is how you get a dreaded TLE (Time Limit Exceeded) or MLE (Memory Limit Exceeded) verdict.

To handle massive graphs, we need to abandon pointer-based nodes and embrace contiguous, array-based data structures.

The Vector Approach

The most common and flexible way to build an adjacency list in C++ is with a vector of vectors. It’s easy to write and understand.

#include <vector>

const int N = 100001;
std::vector<int> adj[N]; // An array of vectors

void add_edge(int u, int v) {
    adj[u].push_back(v);
}

Using an array of std::vector objects is slightly better than a std::vector<std::vector<int>>. The array adj itself is allocated contiguously on the stack or in static memory, which is a small win. However, the underlying data for each individual vector (for each node's neighbors) is still allocated separately on the heap. As you add edges, these vectors can resize and move, fragmenting memory and hurting performance on very large graphs.

The Static Adjacency List

For maximum performance, we can implement a linked list structure using only static arrays. This technique, sometimes called a forward star representation, gives us complete control over memory layout. It involves three main arrays:

Array	Purpose
`head[u]`	Stores the index of the first edge originating from node `u`.
`to[i]`	Stores the destination node (the 'v') for the i-th edge.
`next[i]`	Stores the index of the next edge that also originates from node `u`.

Think of it this way: head is the entry point for a node's edges. From there, you follow the next array like a chain of pointers until you hit the end. All the data lives in three large, contiguous arrays, which is exactly what the CPU cache loves.

Here’s how you build and traverse this structure. We use an edge counter idx to keep track of the next available slot in our edge arrays.

#include <cstring> // For memset

const int N = 100001; // Max nodes
const int M = 200001; // Max edges

int head[N], to[M], next_edge[M], idx;

void init() {
    memset(head, -1, sizeof(head));
    idx = 0;
}

void add_edge(int u, int v) {
    to[idx] = v;
    next_edge[idx] = head[u]; // The new edge points to the old head
    head[u] = idx++;        // The head now points to the new edge
}

// Traversal (e.g., inside a DFS function for node u)
for (int i = head[u]; i != -1; i = next_edge[i]) {
    int v = to[i];
    // Process neighbor v
}

Notice that new edges are added to the front of the list for a given node. This is simpler and faster than finding the end of the list. The order of neighbors usually doesn't matter for most graph algorithms.

Handling Variations

This static structure is also flexible. To handle undirected edges, simply add two directed edges: one from u to v, and one from v to u. This is why our edge array M often needs to be twice the maximum number of edges stated in a problem.

void add_undirected_edge(int u, int v) {
    add_edge(u, v);
    add_edge(v, u);
}

For weighted graphs, just add another array. Let's call it weight. When you add an edge, you store its weight at the same index idx.

int weight[M];

void add_weighted_edge(int u, int v, int w) {
    to[idx] = v;
    weight[idx] = w;
    next_edge[idx] = head[u];
    head[u] = idx++;
}

// Accessing the weight during traversal
for (int i = head[u]; i != -1; i = next_edge[i]) {
    int v = to[i];
    int w = weight[i];
    // Use v and w
}

The key takeaway is that by using parallel arrays, all information for the i-th edge (to[i], next_edge[i], weight[i]) is stored at the same index, i.

Choosing the right graph representation is a classic trade-off between convenience and performance. While std::vector is great for general use, the static adjacency list gives you the raw speed and memory efficiency needed to solve the toughest problems.

Time to check your understanding.

Quiz Questions 1/5

In competitive programming, why is creating a graph by dynamically allocating each Node with new often a bad idea for very large graphs?

Quiz Questions 2/5

What is the primary performance drawback of using a std::vector<std::vector<int>> to represent a large graph?

This foundation in efficient graph representation is critical for implementing high-speed traversals and algorithms.

Tree Representations for Competitive Programming