Chapter 1 · Graphs and Models
Four Ways to Store a Graph
Adjacency list, matrix, edge list, and the compressed variants — with the memory and time each one really costs.
The graph "shape" is a mathematical object; the representation is a trade-off you choose. Pick wrong and an O(n+m) algorithm becomes an O(n2) one — or blows the memory limit.
- Adjacency list:
vector<int> g[n]— neighbours of each vertex. - Adjacency matrix:
bool a[n][n]— is (u,v) an edge? - Edge list:
vector<tuple<int,int,int>>— everything you need for Kruskal/flow. - Incidence / compressed: rows as
bitset, or edges in a hash set — used when n is small but m huge.
| representation | build | edge query | iterate deg(u) | memory | best for |
|---|---|---|---|---|---|
| adjacency list | O(n+m) | O(deg u) | O(deg u) | O(n+m) | traversal, DFS/BFS, Dijkstra |
| adjacency matrix | O(n2) | O(1) | O(n) | O(n2) | n ≤ 2000, Floyd–Warshall, bipartite/complement tricks |
bitset<MAXN> rows | O(n + m) | O(1) | O(n/64) | O(n2/8) | dense graphs, common-neighbour counts |
| edge list | O(m) | — | — | O(m) | MST, colouring, anything sorted by weight |
| hash of edges | O(m) | O(1) avg | O(deg u) | O(m) | implicit graphs (grid states, "complement BFS") |
With bitset, "count common neighbours of u and v" is (adj[u] & adj[v]).count() — O(n/64), i.e. one operation per machine word. Triangle counting drops from O(n3) to O(n3/64), and n=5000 becomes comfortable.
#Contest-grade boilerplate
using ll = long long;
const int MAXN = 200000 + 5; // never guess: derive from the memory limit
vector<int> adj[MAXN]; // undirected: push both ways
vector<tuple<int,int,int>> edges; // (w, u, v) — sort-first algorithms
void add_edge(int u, int v, int w = 1) {
adj[u].push_back(v);
adj[v].push_back(u); // delete this line for digraphs
edges.emplace_back(w, u, v);
}- 2m vs m. An undirected graph stored as lists has 2m entries; a memory limit stated in edges must be doubled before you size arrays.
- Self-loops in lists.
g[u].push_back(u)makes a naive DFS "find a cycle" of length 1. Filterif (v == u) continue;— or keep the loop and mean it (Euler tours do). - Weighted matrix init.
memset(a, 0x3f, sizeof a)gives ~109;memset(…, -1)onintgives -1 bytewise, which is fine, but ondoubleit is garbage. Usenumeric_limits<double>::infinity(). - 1- vs 0-indexed. Input vertices are 1-indexed; either subtract once at read time or size arrays n+1. Never mix.
#Reading input fast
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
vector<int> deg(n);
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++; deg[v]++;
}
}For m ≥ 106 prefer scanf/fread-based readers or store the input as one vector<array<int,2>> and build lists in a second pass — pointer chasing through 2 × 106 small vectors dominates the runtime.
n ≤ 500: matrix, and think about O(n3). n ≤ 5000: matrix as bitset. n ≥ 105 and m = O(n): adjacency list only, and check whether the graph is a tree/functional/planar — that structure is worth more than any micro-optimisation.