templates/graph-representation.cpp
compilable
$cat templates/graph-representation
Graph Representation
Linked-list (head array) adjacency — cache-friendly graph representation for contests.
#graph#adjacency-list#head-array#representation
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define adjLoop(u, v, e) for(int e = head[u], v; ~e && (v = edges[e].to, 1); e = edges[e].nxt)
struct Edge {
int to, nxt, cost;
};
int edgeCount;
vector<Edge> edges;
vector<int> head;
void init(int n, int m) {
edges.resize(2 * m + 5);
head.assign(n + 5, -1);
edgeCount = 1;
}
void addEdge(int u, int v, int c = 0) {
edges[edgeCount] = {v, head[u], c};
head[u] = edgeCount++;
}
void addBiEdge(int u, int v, int c = 0) {
addEdge(u, v, c);
addEdge(v, u, c);
}28 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)
Head-Array Graph Representation
Flat-array linked-list adjacency. Faster than vector due to cache locality and zero heap allocation after init.
How It Works
head[u] points to the first edge index for node ( if none)to, nxt (next edge from same node), and costnxt = head[u], then head[u] = edgeCount++adjLoop(u, v, e) iterates over all neighbors of When to Use
vector> causes TLE due to cache missesNotes
edgeCount starts at 1 (useful for network flow where edge and are reverse pairs)~e is shorthand for e != -1Complexity
addEdge —