Graph Representation

Quick Revisit

• USE WHEN: choosing how to store a graph for traversal, shortest-path, or flow problems
• INVARIANT: adjacency list gives O(V+E) traversal; matrix gives O(1) edge lookup
• TIME: adj list build O(V+E), matrix build O(V^2) | SPACE: adj list O(V+E), matrix O(V^2)
• CLASSIC BUG: forgetting to add both directions for undirected graphs
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

The foundation of every graph problem: how you store the graph determines what algorithms you can run and how fast they execute. Choose wrong and you TLE; choose right and the rest is easy.

In this chapter, the adjacency list is the default. Matrices and edge lists are specialized tools — reach for them when a specific algorithm or constraint demands them, not as coequal first choices.

Difficulty: [Beginner] Prerequisites: Arrays and Strings, Hash Map and Unordered MapCF Rating Range: 1000-1300 ID: AL-11

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Recap
• Further Reading

---

Intuition

Consider a directed graph with 5 nodes and 6 edges:

       1 ----> 2
       |      /|
       |     / |
       v    v  v
       3 <--- 4
        \
         v
          5

  Edges: (1,2) (1,3) (2,4) (4,2) (4,3) (3,5)

Task: find all neighbors of node 2.

Adjacency matrix -- store a $5\times 5$ grid of booleans:

  mat[2][?]:  0  0  0  1  0
              ^  ^  ^  ^  ^
              1  2  3  4  5

  Must scan all 5 entries to discover the single neighbor {4}.

That is $O(n)$ per query. Now imagine BFS: every time you pop a node, you scan its entire row. For $n=5$ and $m=6$, BFS visits all 5 nodes and scans $5\times 5=25$ cells total -- but only 6 edges actually exist. 19 wasted checks.

Edge list -- store all edges in a flat array:

  edges: [(1,2), (1,3), (2,4), (4,2), (4,3), (3,5)]

  To find neighbors of node 2, scan ALL 6 edges.
  Only (2,4) starts at 2.  5 wasted comparisons.

That is $O(m)$ per query. BFS pops 5 nodes, each time scanning all 6 edges: $5\times 6=30$ total operations for a tiny graph. This scales to $O(n\cdot m)$ -- catastrophic.

The adjacency list gives $O(\mathrm{deg}(v))$ neighbor access by storing only the edges that exist.

Think of it like your phone contacts list versus the full phone book. The phone book has an entry for every person in the city -- to find who you call, you would scan millions of rows (adjacency matrix). An unsorted pile of everyone's call records forces you to sift through all calls to find yours (edge list). Your contacts list contains exactly the people you talk to, nothing more (adjacency list).

The analogy breaks when you need to ask "does person X know person Y?" -- a contacts list requires a linear scan through X's contacts ($O(\mathrm{deg}(X))$), while the phone book answers in $O(1)$. For BFS, DFS, Dijkstra, and topological sort you never need that query, so the tradeoff is almost always worth it.

Visual Walkthrough

Build the adjacency list for the same graph step by step.

Step 1 -- Allocate. Create an array of 6 empty lists (index 0 unused, 1-indexed to match CF conventions):

  adj[1]: []    adj[2]: []    adj[3]: []    adj[4]: []    adj[5]: []

Step 2 -- Insert edges. Process each edge $(u,v)$ by appending $v$ to adj[u]:

  Edge (1,2):  adj[1]: [2]
  Edge (1,3):  adj[1]: [2, 3]
  Edge (2,4):  adj[2]: [4]
  Edge (4,2):  adj[4]: [2]
  Edge (4,3):  adj[4]: [2, 3]
  Edge (3,5):  adj[3]: [5]

Step 3 -- Query neighbors of node 2. Read adj[2]:

  adj[2]: [4]    -->  1 element, 1 operation.

Compare: the matrix scanned 5 cells, the edge list scanned 6 entries. The adjacency list touched exactly $\mathrm{deg}(2)=1$ element.

Step 4 -- Full BFS cost comparison. BFS visits every node once and iterates its adjacency list:

  Node  | deg | ops (adj list) | ops (matrix) | ops (edge list)
  ------+-----+----------------+--------------+----------------
    1   |  2  |       2        |      5       |       6
    2   |  1  |       1        |      5       |       6
    3   |  1  |       1        |      5       |       6
    4   |  2  |       2        |      5       |       6
    5   |  0  |       0        |      5       |       6
  ------+-----+----------------+--------------+----------------
  Total |  6  |       6        |     25       |      30

Adjacency list: $n+m=5+6=11$ work (including the 5 pops). Matrix: $n^2=25$. Edge list: $n\cdot m=30$.

Three Representations Side-by-Side

The same directed graph -- edges (1,2) (1,3) (2,4) (4,2) (4,3) (3,5) -- stored three different ways:

+---------------------------+  +------------------+  +------------------+
|     ADJACENCY MATRIX      |  |  ADJACENCY LIST  |  |    EDGE LIST     |
+---------------------------+  +------------------+  +------------------+
|       1   2   3   4   5   |  |                  |  |                  |
|     +---+---+---+---+---+ |  |  1 -> [2, 3]     |  |  (1, 2)         |
|  1  | . | # | # | . | . | |  |  2 -> [4]        |  |  (1, 3)         |
|     +---+---+---+---+---+ |  |  3 -> [5]        |  |  (2, 4)         |
|  2  | . | . | . | # | . | |  |  4 -> [2, 3]     |  |  (4, 2)         |
|     +---+---+---+---+---+ |  |  5 -> []         |  |  (4, 3)         |
|  3  | . | . | . | . | # | |  |                  |  |  (3, 5)         |
|     +---+---+---+---+---+ |  +------------------+  +------------------+
|  4  | . | # | # | . | . | |  | 6 neighbor ints  |  | 12 ints (6 pairs)|
|     +---+---+---+---+---+ |  | + 5 list heads   |  |                  |
|  5  | . | . | . | . | . | |  | = O(V + E)       |  | = O(E)           |
|     +---+---+---+---+---+ |  |                  |  |                  |
| 25 cells = O(V^2)         |  | Neighbor scan:   |  | Neighbor scan:   |
| # = edge    . = no edge   |  |   O(deg(u))      |  |   O(E) per node  |
| Edge check: O(1)          |  | Edge check:      |  | Edge check:      |
| Neighbor scan: O(V)       |  |   O(deg(u))      |  |   O(E)           |
+---------------------------+  +------------------+  +------------------+

Memory Layout: vector<vector<int>>

How adj actually lives in memory after building the adjacency list:

  adj: vector<vector<int>>     (n+1 = 6 slots, index 0 unused)

  Stack / outer vector:
  +--------+--------+--------+--------+--------+--------+
  | adj[0] | adj[1] | adj[2] | adj[3] | adj[4] | adj[5] |
  | ptr    | ptr----+> heap  | ptr--+>| ptr--+>| ptr--+>| ptr    |
  +--------+--------+--------+--------+--------+--------+
              |         |        |        |        |
              v         v        v        v        v
           +-----+   +-----+  +-----+ +-----+  +-----+
           |  2  |   |  4  |  |  5  | |  2  |  |     |
           +-----+   +-----+  +-----+ +-----+  +-----+
           |  3  |                     |  3  |   empty
           +-----+                     +-----+
           size=2     size=1   size=1  size=2   size=0

  * Each adj[u] is a separate heap-allocated array
  * Iterating adj[u]: one pointer chase -> sequential scan
  * Total memory: 6 vector headers + 6 ints stored = O(V + E)
  * This is why "for (int v : adj[u])" is cache-friendly
    per-node but adj[1] and adj[2] may be far apart in memory

Weighted Adjacency List in Memory

How vector<vector<pair<int,int>>> wadj stores a weighted graph:

  Graph:  1 --5-- 2 --3-- 3
          |               |
          7               1
          |               |
          4 ------2------ 5

  wadj[1]: [(2,5), (4,7)]      wadj[2]: [(1,5), (3,3)]
  wadj[3]: [(2,3), (5,1)]      wadj[4]: [(1,7), (5,2)]
  wadj[5]: [(3,1), (4,2)]

  In memory (each pair = 8 bytes on 32-bit int):

  wadj[1]              wadj[2]              wadj[3]
  +------+------+      +------+------+      +------+------+
  |nbr: 2|wt: 5 |      |nbr: 1|wt: 5 |      |nbr: 2|wt: 3 |
  +------+------+      +------+------+      +------+------+
  |nbr: 4|wt: 7 |      |nbr: 3|wt: 3 |      |nbr: 5|wt: 1 |
  +------+------+      +------+------+      +------+------+

  Access: for (auto [v, w] : wadj[u]) { ... }
  Space: O(V + 2E) pairs for undirected weighted graph.

Grid-to-Graph Mapping

A grid is an implicit graph -- no adjacency list is built. Each cell (r, c) has up to 4 neighbors computed on the fly:

  3x4 Grid:                     Implicit neighbor map for cell (1,2):
  +---+---+---+---+
  | . | . | # | . |  row 0          (0,2) = '#' -> blocked
  +---+---+---+---+                    ^
  | . | . | . | . |  row 1     (1,1) <-- (1,2) --> (1,3)
  +---+---+---+---+                    v
  | # | . | . | . |  row 2          (2,2) = '.' -> open
  +---+---+---+---+
   c0   c1  c2  c3

  dx[] = {-1, 1,  0, 0}         Neighbor check for (1,2):
  dy[] = { 0, 0, -1, 1}           up    (0,2): '#' -> skip
                                   down  (2,2): '.' -> valid
  for (int d = 0; d < 4; d++)     left  (1,1): '.' -> valid
    nx = r + dx[d]                 right (1,3): '.' -> valid
    ny = c + dy[d]
    if (in_bounds && !wall)      Result: 3 valid neighbors
       -> process (nx, ny)       No adjacency list was built!

The Invariant

+------------------------------------------------------------------+
|  adj[u] contains exactly the neighbors of u                      |
|  (with weights if applicable).                                   |
|  Total storage = O(n + m).                                       |
+------------------------------------------------------------------+

Every edge $(u,v)$ appears exactly once in adj[u] (directed) or once in each of adj[u] and adj[v] (undirected, so $2m$ entries total). No slot is wasted on non-existent edges.

From the walkthrough: 5 lists with 6 total entries = $O(5+6)=O(n+m)$. Iterating all neighbors of all nodes visits each entry once -- this is why BFS and DFS run in $O(n+m)$.

What the Code Won't Teach You

The representation determines what operations are O(1) vs O(V).

Most tutorials show how to build an adjacency list but never explain why it's the default. The reason is algorithmic: BFS, DFS, Dijkstra, and topological sort all need one operation -- "iterate neighbors of u" -- and the adjacency list makes that O(deg(u)). The matrix makes it O(V), and the edge list makes it O(E). For sparse graphs where E << V^2, this difference is the gap between AC and TLE.

Conversely, the adjacency matrix gives O(1) edge-existence checks that the adjacency list cannot match. Floyd-Warshall needs d[i][k] + d[k][j] in an inner loop -- naturally a matrix access. Forcing an adjacency list into Floyd-Warshall means you'd reconstruct a matrix anyway.

When to use which representation -- the decision tree:

  Read the problem constraints:
        |
        v
  +------------------+     YES     +-------------------+
  | V <= 500 and need +----------->| Adjacency MATRIX  |
  | all-pairs paths?  |            | (Floyd-Warshall)  |
  +------------------+            +-------------------+
        | NO
        v
  +------------------+     YES     +-------------------+
  | Need to sort all  +----------->| EDGE LIST         |
  | edges by weight?  |            | (Kruskal, B-Ford) |
  +------------------+            +-------------------+
        | NO
        v
  +------------------+     YES     +-------------------+
  | V can be >= 10^4? +----------->| Adjacency LIST    |
  | (most problems)   |            | (BFS/DFS/Dijkstra)|
  +------------------+            +-------------------+
        | NO
        v
  +------------------+
  | Either list or    |
  | matrix works.     |
  | Prefer list.      |
  +------------------+

With that mental model in place, here is how to recognize which representation a problem needs.

When to Reach for This

Trigger phrases in problem statements:

• "given a graph with $n$ nodes and $m$ edges"
• "read $m$ edges" / "graph input"
• "adjacency list" (stated explicitly)
• "BFS", "DFS", "shortest path (unweighted)", "connected components", "topological sort", "Dijkstra"

If you see any of these and $n$ can be up to $2\times {10}^5$, the adjacency list is the default -- do not even consider alternatives.

Counter-examples (when the matrix wins):

• $n\le 500$ and you need all-pairs shortest paths (Floyd-Warshall requires a matrix).
• $n\le 2000$ and you need $O(1)$ edge-existence checks or bitwise row operations (bitset<N> adj[N]).
• For larger $n$ with frequent edge-existence queries, sort each adjacency list and binary-search ($O(\log \mathrm{deg}(u))$), or use unordered_set<int> per node.
• The graph is dense ($m\approx n^2$) -- the matrix wastes no space and gives faster cache behavior.

Counter-example (when the edge list wins):

• Kruskal's MST: sort edges by weight globally -- an adjacency list scatters them across $n$ buckets.
• Bellman-Ford: relax all edges $n-1$ times -- a flat edge array is simpler and cache-friendly.

Input Taxonomy: Reading the Problem Before You Build

Before allocating anything, classify the input on four axes. Each one flips a switch in your build code:

Axis	Options	Effect on adjacency list
Weighted?	unweighted / weighted	vector<vector<int>> vs vector<vector<pair<int,int>>>
Direction	directed / undirected	push once, or push both u→v and v→u
Indexing	0-indexed / 1-indexed	allocate adj(n) vs adj(n+1)
Density	sparse ($m\approx n$) / dense ($m\approx n^2$)	list for sparse, matrix becomes viable for dense + small $n$

Two more flags worth scanning for: self-loops allowed? Multi-edges allowed? Both are handled cleanly by adjacency lists, but they may break code that silently assumes simple graphs.

From Problem Statement to Adjacency Structure

Three small examples of translating a statement into a build:

Example 1 — undirected unweighted, 1-indexed:

"You are given $n$ cities and $m$ two-way roads. The $i$-th road connects cities $u_i$ and $v_i$."

int n, m; cin >> n >> m;
vector<vector<int>> adj(n + 1);              // 1-indexed
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);                      // two-way
}

Example 2 — directed weighted, 1-indexed:

"There are $n$ rooms and $m$ one-way teleporters. Each teleporter goes from $u$ to $v$ and costs $w$ energy."

int n, m; cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].emplace_back(v, w);                // one-way only
}

Example 3 — tree given as parent array, 0-indexed:

"Node 0 is the root. For each node $i=1\dots n-1$, you are given $p_i$, the parent of $i$."

int n; cin >> n;
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) {
    int p; cin >> p;
    adj[p].push_back(i);
    adj[i].push_back(p);                      // tree is undirected
}

Notice what changes: the type of adj, whether you push both directions, and the size you allocate. Everything else is the same. The translation is mechanical once you have read the four axes off the statement.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
vector<vector<int>> adj(n+1)	<vector>	Adjacency list for unweighted graph	$O(n)$ construction
vector<vector<pair<int,int>>> adj(n+1)	<vector>	Adjacency list for weighted graph (neighbor, weight)	$O(n)$ construction
adj[u].push_back(v)	<vector>	Add edge $u\to v$	$O(1)$ amortized
adj[u].emplace_back(v, w)	<vector>	Add weighted edge $u\to v$ with weight $w$	$O(1)$ amortized
vector<tuple<int,int,int>> edges	<vector>, <tuple>	Edge list (u, v, weight)	$O(1)$ per push
vector<array<int,2>> adj[N]	<vector>, <array>	Alternative: array-based adjacency list	$O(1)$ per push
sort(edges.begin(), edges.end())	<algorithm>	Sort edge list (by first element, then second, ...)	$O(m\log m)$
adj[u].size()	<vector>	Degree of node $u$	$O(1)$
adj[u].clear()	<vector>	Remove all edges from $u$	$O(\mathrm{deg}(u))$
bitset<N> adj[N]	<bitset>	Adjacency matrix with bitset (fast bitwise ops)	$O(n/64)$ per row op

---

Implementation (Contest-Ready)

Version 1: Minimal Contest Template

Directed + Undirected + Weighted -- all three patterns in one file.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // --- Unweighted directed adjacency list ---
    vector<vector<int>> directed(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        directed[u].push_back(v);
    }

    // --- Unweighted undirected adjacency list ---
    // (re-read input or modify above; shown separately for clarity)
    vector<vector<int>> undirected(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        undirected[u].push_back(v);
        undirected[v].push_back(u);  // <-- the reverse edge
    }

    // --- Weighted directed adjacency list ---
    vector<vector<pair<int,int>>> weighted(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        weighted[u].emplace_back(v, w);
    }

    // --- Edge list (weighted) ---
    vector<tuple<int,int,int>> edges(m);
    for (auto& [u, v, w] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
        return get<2>(a) < get<2>(b);  // sort by weight
    });

    // --- Adjacency matrix (small n only) ---
    // vector<vector<int>> mat(n + 1, vector<int>(n + 1, 0));
    // for (int i = 0; i < m; i++) {
    //     int u, v; cin >> u >> v;
    //     mat[u][v] = 1;
    //     // mat[v][u] = 1;  // uncomment for undirected
    // }

    return 0;
}

Version 2: Explained Version

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // n = number of nodes (typically 1-indexed on CF)
    // m = number of edges

    // ADJACENCY LIST (unweighted, undirected)
    // -----------------------------------------
    // Why n+1? Because CF problems use 1-indexed nodes.
    // adj[0] is wasted but avoids off-by-one bugs.
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
        // For DIRECTED graphs: remove the second line.
        // Every undirected edge is stored TWICE.
        // Total memory: O(n + 2m).
    }

    // Iterating neighbors of node u:
    // for (int v : adj[u]) { ... }
    // This is O(deg(u)) -- exactly what BFS/DFS needs.

    // ADJACENCY LIST (weighted, directed)
    // ------------------------------------
    // pair.first = neighbor, pair.second = weight
    // Some people use {weight, neighbor} for Dijkstra priority queue
    // compatibility -- be consistent within your code.
    vector<vector<pair<int,int>>> wadj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        wadj[u].emplace_back(v, w);
        // emplace_back constructs the pair in-place, slightly faster
        // than push_back({v, w}) but both work.

        // For undirected weighted: also do wadj[v].emplace_back(u, w);
    }

    // Iterating weighted neighbors:
    // for (auto [v, w] : wadj[u]) { ... }
    // Structured bindings (C++17) make this clean.

    // EDGE LIST (weighted)
    // ---------------------
    // Useful when you need to process edges globally:
    //   - Kruskal: sort by weight, iterate
    //   - Bellman-Ford: relax all edges repeatedly
    vector<tuple<int,int,int>> edges;
    edges.reserve(m);  // optional: avoids reallocations

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }

    // Sort by weight (third element):
    sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
        return get<2>(a) < get<2>(b);
    });

    // Access with structured bindings:
    // for (auto [u, v, w] : edges) { ... }

    // ADJACENCY MATRIX (small n only, n <= ~2000)
    // ---------------------------------------------
    // Use when you need O(1) edge existence checks or Floyd-Warshall.
    // WARNING: O(n^2) memory. For n=200000 this is 40GB -- instant MLE.
    const int MAXN = 505;  // adjust to problem constraints
    int mat[MAXN][MAXN] = {};
    // All zeros by default (no edges).

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        mat[u][v] = 1;
        mat[v][u] = 1;  // undirected
    }

    // Check edge: if (mat[u][v]) { ... }  -- O(1)
    // Iterate neighbors: for (int v=1; v<=n; v++) if (mat[u][v]) ...  -- O(n)

    return 0;
}

Bonus: Grid as implicit graph (very common on CF)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (auto& row : grid) cin >> row;

    // 4-directional movement
    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};

    // BFS from (0, 0)
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int,int>> q;
    dist[0][0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    return 0;
}

---

Operations Reference

Each representation optimizes for different operations. This table shows the cost of the operations that matter most in contest problems -- use it to pick the right structure.

Operation	Adj. List	Edge List	Adj. Matrix	Implicit (Grid)
Add edge	$O(1)$	$O(1)$	$O(1)$	N/A
Check edge $(u,v)$	$O(\mathrm{deg}(u))$	$O(m)$	$O(1)$	$O(1)$
Iterate neighbors of $u$	$O(\mathrm{deg}(u))$	$O(m)$	$O(n)$	$O(4)$ or $O(8)$
Iterate all edges	$O(n+m)$	$O(m)$	$O(n^2)$	$O(n\cdot m)$
Space	$O(n+m)$	$O(m)$	$O(n^2)$	$O(n\cdot m)$
Remove edge	$O(\mathrm{deg}(u))$	$O(m)$	$O(1)$	N/A
BFS/DFS total	$O(n+m)$	$O(n\cdot m)$	$O(n^2)$	$O(n\cdot m)$

---

Problem Patterns & Tricks

Pattern 1: BFS/DFS on Adjacency List

The bread-and-butter. Read graph, build adjacency list, run BFS or DFS. Covers connected components, shortest path in unweighted graphs, cycle detection.

// Standard BFS skeleton
vector<int> dist(n + 1, -1);
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

Examples: CF 1037C, CF 580C

Pattern 2: Edge List + Sort (Kruskal's MST)

Read all edges into a flat list, sort by weight, iterate with DSU. The edge list representation is purpose-built for this.

  Edge list before sort:           After sort by weight:
  +-----+-----+--------+          +-----+-----+--------+
  | u   | v   | weight |          | u   | v   | weight |
  +-----+-----+--------+          +-----+-----+--------+
  | 1   | 2   |   7    |          | 2   | 3   |   1    |  <-- pick (union)
  | 2   | 3   |   1    |          | 3   | 4   |   3    |  <-- pick (union)
  | 3   | 4   |   3    |          | 1   | 4   |   5    |  <-- pick (union)
  | 1   | 4   |   5    |          | 1   | 2   |   7    |  <-- skip (cycle)
  | 1   | 3   |   9    |          | 1   | 3   |   9    |  <-- skip (cycle)
  +-----+-----+--------+          +-----+-----+--------+
                                   MST weight = 1 + 3 + 5 = 9

sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
    return get<2>(a) < get<2>(b);
});
for (auto [u, v, w] : edges) {
    if (find(u) != find(v)) { unite(u, v); mst_weight += w; }
}

Examples: CF 472D, CF 1245D

Pattern 3: Grid BFS (Implicit Graph)

The grid is the graph. Each cell is a node, 4 (or 8) neighbors. No explicit adjacency list needed. Extremely common at 1000-1400 rating.

Examples: CF 1063B, CF 1293A

Pattern 4: Bipartite Check via BFS/DFS

Build adjacency list, 2-color with BFS. If you find a conflict, the graph is not bipartite.

vector<int> color(n + 1, -1);
bool bipartite = true;
for (int i = 1; i <= n && bipartite; i++) {
    if (color[i] != -1) continue;
    queue<int> q; q.push(i); color[i] = 0;
    while (!q.empty() && bipartite) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
            else if (color[v] == color[u]) bipartite = false;
        }
    }
}

Examples: CF 687A, CF 1093D

Pattern 5: Multi-source BFS

Add all source nodes to the queue at distance 0 before starting BFS. Works on adjacency list, grid, or any representation.

Examples: CF 1293D, CF 1316B

Pattern 6: Adjacency Matrix + Floyd-Warshall

When $n\le 500$, store the graph as a matrix and run Floyd-Warshall for all-pairs shortest paths.

// dist[i][j] initialized to INF, dist[i][i] = 0, dist[u][v] = w for edges
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Examples: CF 295B, CF 1204C

Pattern 7: Storing Extra Info per Edge

When edges carry data (capacity, color, index), use struct or tuple in the adjacency list. For flow networks, store reverse-edge indices.

struct Edge { int to, cap, rev; };
vector<vector<Edge>> graph(n + 1);
auto add_edge = [&](int u, int v, int cap) {
    graph[u].push_back({v, cap, (int)graph[v].size()});
    graph[v].push_back({u, 0, (int)graph[u].size() - 1});
};

Examples: CF 653D

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                  GRAPH REPRESENTATION                        |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|  * Adj list: BFS, DFS, Dijkstra, topo-sort (default)        |
|  * Edge list: Kruskal, Bellman-Ford                          |
|  * Adj matrix: Floyd-Warshall, n <= 2000                     |
|  * Grid: implicit graph, no build step                       |
+--------------------------------------------------------------+
| KEY CODE:                                                    |
|  vector<vector<int>> adj(n+1);        // unweighted          |
|  adj[u].push_back(v);                 // directed edge       |
|  adj[v].push_back(u);                 // + undirected        |
|  vector<vector<pair<int,int>>> w(n+1);// weighted            |
|  w[u].emplace_back(v, cost);          // directed+weighted   |
+--------------------------------------------------------------+
| COMPLEXITY:                                                  |
|  Adj list:  O(n+m) space, O(deg) per neighbor scan           |
|  Edge list: O(m) space, O(m) per scan                        |
|  Matrix:    O(n^2) space, O(1) edge check, O(n) per scan     |
+--------------------------------------------------------------+
| GOTCHAS:                                                     |
|  * Use adj(n+1) for 1-indexed nodes                          |
|  * Undirected = push BOTH directions                         |
|  * Self-loops: push_back adds u to adj[u]                    |
+--------------------------------------------------------------+

---

Gotchas & Debugging

1. 1-indexed vs 0-indexed

CF problems almost always use 1-indexed nodes. Allocate adj(n + 1), not adj(n). If you see a runtime error or wrong answer, check this first.

2. Forgetting the reverse edge for undirected graphs

The single most common bug for beginners. If the problem says "undirected" or "bidirectional," you must add both adj[u].push_back(v) and adj[v].push_back(u). Forgetting this makes half your graph unreachable.

  Undirected graph:  1 --- 2 --- 3 --- 4
                     |                 |
                     +-----------------+

  Edges: (1,2) (2,3) (3,4) (1,4)

  BUG: only added adj[u].push_back(v), forgot reverse:
    adj[1] = [2, 4]    adj[2] = [3]    adj[3] = [4]    adj[4] = []

  BFS from node 3:
  +-------+-------------------+-------------------+------------------+
  | Step  | Queue             | Visit             | Result           |
  +-------+-------------------+-------------------+------------------+
  |   0   | [3]               | --                | start            |
  |   1   | [4]               | 3 -> adj[3]=[4]   | push 4           |
  |   2   | []                | 4 -> adj[4]=[]    | no neighbors!    |
  +-------+-------------------+-------------------+------------------+
  Visited: {3, 4}     Missing: {1, 2}  <--- WRONG!
        ^                        ^
        |                        |
        +--- only 2 of 4 -------+--- nodes 1,2 unreachable
             nodes found              because no edge points TO them

  FIX: add both directions:
    adj[1] = [2, 4]  adj[2] = [1, 3]  adj[3] = [2, 4]  adj[4] = [3, 1]

  BFS from node 3 (corrected):
    Visit 3 -> push 2, 4
    Visit 2 -> push 1
    Visit 4 -> 3 seen, 1 seen
    Visit 1 -> 2 seen, 4 seen
  Visited: {3, 2, 4, 1}  <--- CORRECT, all 4 nodes found

3. Self-loops and multi-edges

Some problems allow edge $(u,u)$ or multiple edges between the same pair. If your algorithm assumes simple graphs, check the constraints. Adjacency lists handle multi-edges naturally; adjacency matrices silently merge them.

4. Integer overflow on weighted graphs

Edge weights up to ${10}^9$, path lengths up to $n\cdot {10}^9$ where $n=2\cdot {10}^5$. That exceeds int. Use long long for distances.

5. Reading input format wrong

Some problems give edges as "parent array" (for trees), some as adjacency list already, some as grid. Read the input format carefully. A tree with $n$ nodes has $n-1$ edges -- if you try to read $m$ edges and $m$ isn't given, you'll read garbage.

6. Clearing the graph between test cases

Multi-test problems (t test cases): you must clear the adjacency list between cases. Either adj[u].clear() for all used nodes, or re-create the vector with adj.assign(n + 1, {}).

// Safe reset for multi-test:
int t; cin >> t;
while (t--) {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n + 1);  // fresh each test case
    // ... read edges ...
}

7. Edge index tracking

Some problems ask "which edges are in the answer?" Store the edge index alongside the edge. Use adj[u].push_back({v, i}) and remember i during traversal.

Mental Traps

Trap 1: "I added the edge, so both directions work."

For undirected graphs, adj[u].push_back(v) alone creates a directed edge. You must also add adj[v].push_back(u). Visualize the asymmetry:

  Undirected edge (2, 5):

  CORRECT (both directions):          BUG (one direction only):

    2 ---------- 5                      2 ---------> 5
    adj[2] = [5]                        adj[2] = [5]
    adj[5] = [2]                        adj[5] = []
         ^                                   ^
         |                                   |
    2 can reach 5  *and*               2 can reach 5  but
    5 can reach 2                      5 CANNOT reach 2
                                            |
                                            +---> BFS from 5 never
                                                  finds node 2!

Trap 2: "Adjacency list is always better than adjacency matrix."

Wrong. Visualize the trade-off:

  SPARSE graph: V=6, E=5               DENSE graph: V=4, E=6 (complete)

  Adj Matrix (6x6 = 36 cells):         Adj Matrix (4x4 = 16 cells):
  +---+---+---+---+---+---+            +---+---+---+---+
  | . | # | . | . | . | . |            | . | # | # | # |
  +---+---+---+---+---+---+            +---+---+---+---+
  | # | . | # | . | . | . |            | # | . | # | # |
  +---+---+---+---+---+---+            +---+---+---+---+
  | . | # | . | . | # | . |            | # | # | . | # |
  +---+---+---+---+---+---+            +---+---+---+---+
  | . | . | . | . | # | . |            | # | # | # | . |
  +---+---+---+---+---+---+            +---+---+---+---+
  | . | . | # | # | . | # |            Most cells are #
  +---+---+---+---+---+---+            --> matrix wastes nothing
  | . | . | . | . | # | . |            --> O(1) edge lookup wins
  +---+---+---+---+---+---+
  Mostly dots (wasted space)
  --> adj list wins: only 10 entries

  # = edge exists    . = wasted O(V^2) slot

Trap 3: "My nodes start at 1, but I allocated adj(n) -- close enough."

Off-by-one between 0-indexed and 1-indexed causes silent corruption:

  Problem: nodes 1, 2, 3       n = 3

  adj(n) = adj(3)  -->  valid indices: [0] [1] [2]
  Input edge: (3, 1)
  adj[3].push_back(1)  -->  OUT OF BOUNDS!  index 3 doesn't exist
                             |
                             +---> undefined behavior: may crash,
                                   may silently corrupt memory

  FIX: adj(n + 1)   -->  valid indices: [0] [1] [2] [3]
       adj[3].push_back(1)  -->  OK!
       (index 0 is unused but safe)

Pre-Flight Checklist

Before submitting, verify:

1. Directed or undirected? If undirected, did you add both u->v and v->u?
2. 0-indexed or 1-indexed? Does your array size match? (n vs n+1)
3. Self-loops or multi-edges? Does the problem allow them? Does your code handle them?
4. Weight type: int or long long? Will edge weights overflow during summation?
5. Memory budget: For $n=2\times {10}^5$, adjacency list is ~4 MB; a matrix would be ~40 GB.

---

Self-Test

Without looking at the code above, answer these from memory.

1. Build it. Given 4 nodes and undirected edges (1,2) (2,3) (3,4) (1,4), write out the full adjacency list (1-indexed). How many total entries should there be?

2. Spot the bug. You declared vector<vector<int>> adj(n) for a 1-indexed problem with nodes 1..n. What goes wrong and how do you fix it?

3. Choose the representation. You need to run Kruskal's MST on a graph with $n={10}^5$ nodes. Do you use an adjacency list, adjacency matrix, or edge list? Why?

4. Complexity check. What is the time complexity of BFS using an adjacency list? Using an adjacency matrix? Using an edge list? State all three.

5. Multi-test trap. You have t test cases and a global vector<vector<int>> adj. After solving test case 1, what must you do before test case 2? Write the code.

6. Weighted edges. How do you modify vector<vector<int>> adj to store edge weights? Write the type and the insertion line for a directed edge u -> v with weight w.

7. Matrix vs list. For Floyd-Warshall on $n=400$ nodes, which representation do you use? What about for BFS on $n=2\times {10}^5$? Justify both answers.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Counting Rooms	CSES	Easy	Grid BFS, connected components
2	Building Roads	CSES	Easy	Adj list, count connected components
3	CF 580C - Kefa and Park	Codeforces	Easy	Tree adj list, DFS
4	CF 1037C - Equalize	Codeforces	Easy-Med	BFS on adj list
5	CF 687A - NP-Hard Problem	Codeforces	Medium	Bipartite check via adj list
6	CF 1245D - Shichikuji and Power Grid	Codeforces	Medium	Edge list + MST
7	CF 295B - Greg and Graph	Codeforces	Medium	Adj matrix, reverse Floyd-Warshall
8	CF 1093D - Beautiful Graph	Codeforces	Medium	Bipartite + counting
9	Shortest Routes I	CSES	Medium	Weighted adj list + Dijkstra
10	CF 1063B - Labyrinth	Codeforces	Hard	Grid BFS with deque (0-1 BFS)

---

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	Read $n,m$, build adjacency list, run BFS/DFS
1500	Weighted adjacency list, 0-indexed vs 1-indexed, undirected double-add
1800	Implicit graphs (grids, state-space), compressed adjacency, functional graphs
2100	Edge list tricks (Kruskal rebuild tree), CSR for cache performance, virtual nodes

Debug This

Bug 1: Why does this crash on the first test case?

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;  // 1-indexed input
    adj[u].push_back(v);
    adj[v].push_back(u);
}

Answer

The adjacency list has size n (indices 0 to $n-1$), but input is 1-indexed, so adj[n] is out of bounds. Fix: use vector<vector<int>> adj(n + 1) or convert to 0-indexed with adj[u-1].push_back(v-1).

Bug 2: This code builds a weighted adjacency list, but Dijkstra gives wrong answers:

vector<vector<pair<int,int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}
// Later in Dijkstra:
for (auto [w, v] : adj[u]) { ... }  // destructured as (weight, vertex)

Answer

The pair is stored as {vertex, weight} but destructured as {weight, vertex}. The order is inconsistent. Fix: either store as {weight, vertex} or destructure as {vertex, weight}. Pick one convention and stick to it everywhere.

Bug 3: Memory limit exceeded on $n={10}^5$:

int adj[100001][100001];  // adjacency matrix

Answer

A ${10}^5\times {10}^5$ integer matrix requires ${10}^{10}\times 4=40$ GB. Use an adjacency list instead. Adjacency matrix is only viable for $n\le 2000$-$5000$ depending on memory limits.

Historical Origin

The adjacency list representation was formalized by John Hopcroft and Robert Tarjan in the early 1970s as part of their foundational work on efficient graph algorithms. The adjacency matrix dates back to the origins of graph theory itself -- Arthur Cayley and James Joseph Sylvester used matrix representations of graphs in the 19th century.

Mnemonic Anchor

"List for speed, matrix for lookup, edge-list for sorting." Three representations, three superpowers. Match the tool to the task.

---

Recap

• Adjacency list is the default for contest graphs: O(V+E) space, O(deg(u)) neighbor scan -- use for BFS, DFS, Dijkstra, topological sort.
• Adjacency matrix gives O(1) edge lookup at O(V^2) space cost -- use for Floyd-Warshall or dense graphs with small V.
• Edge list stores edges flat for global processing -- use for Kruskal's MST and Bellman-Ford.
• Grids are implicit graphs -- compute neighbors on the fly with dx/dy arrays, no explicit build step.
• The #1 bug: forgetting the reverse edge for undirected graphs. The #2 bug: adj(n) instead of adj(n+1) for 1-indexed nodes.
• Match the representation to the algorithm's bottleneck operation, not to habit.

---

Further Reading

• cp-algorithms: Graph Representation -- comprehensive reference with alternate representations.
• cp-algorithms: BFS -- natural next step after learning representation.
• CSES Graph Section -- excellent progressive problem set for all graph topics.
• CF Blog: How to solve graph problems -- practical CF-oriented advice.

Next topics:

• See: BFS
• See: DFS and Tree DFS
• See: Dijkstra
• See: MST -- Kruskal
• See: Graph Modeling Guide
• See: Practice Ladder -- Graphs