---
title: Four Ways to Store a Graph
summary: Adjacency list, matrix, edge list, and the compressed variants — with the memory and time each one really costs.
difficulty: easy
tags: [implementation, memory]
time: n + m
space: n + m
see: [foundations/types, trees/dfs, advanced-tree/mst]
---

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(n^2)$ one — or blows the memory limit.

:::definition label="The four candidates"
- **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(n^2)$ | $O(1)$ | $O(n)$ | $O(n^2)$ | $n \le 2000$, Floyd–Warshall, bipartite/complement tricks |
| `bitset<MAXN>` rows | $O(n + m)$ | $O(1)$ | $O(n/64)$ | $O(n^2/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") |

:::note title="The 64× trick"
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(n^3)$ to $O(n^3/64)$, and $n=5000$ becomes comfortable.
:::

## Contest-grade boilerplate

```cpp graph.hpp
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);
}
```

:::warning title="Four bugs that survive every reviewer"
1. **$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.
2. **Self-loops in lists.** `g[u].push_back(u)` makes a naive DFS "find a cycle" of length 1. Filter `if (v == u) continue;` — or keep the loop and mean it (Euler tours do).
3. **Weighted matrix init.** `memset(a, 0x3f, sizeof a)` gives ~$10^9$; `memset(…, -1)` on `int` gives $-1$ bytewise, which is fine, but on `double` it is garbage. Use `numeric_limits<double>::infinity()`.
4. **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

```cpp io.cpp
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 \ge 10^6$ 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 \times 10^6$ small vectors dominates the runtime.

:::problems
- [[CSES 1192]] Counting Rooms | https://cses.fi/problemset/task/1192 | easy | grid, components
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | components + DSU
- [[SPOJ PT07Y]] Is it a tree? | https://www.spoj.com/problems/PT07Y/ | easy | m = n-1 + connectivity
:::

:::tip title="Rule of thumb"
$n \le 500$: matrix, and think about $O(n^3)$. $n \le 5000$: matrix as `bitset`. $n \ge 10^5$ 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.
:::

:::figure src="Simple_Graph.svg" caption="The running example for this chapter: a connected, undirected, unweighted graph. Its adjacency list has 2·|E| entries; its matrix is symmetric with an all-zero diagonal."
:::