Graph Representation

Linked-list (head array) adjacency — cache-friendly graph representation for contests.

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#graph#adjacency-list#head-array#representation

$cat source_code/

cpp

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

#define adj_loop(u, v, e) for (int e = head[u], v; ~e && (v = edges[e].to, 1); e = edges[e].nxt)

template <typename T = int>
struct edgeData {
  T to, nxt, cost;
  edgeData(T TO = 0, T NXT = 0, T COST = 0) : to(TO), nxt(NXT), cost(COST) {}
};

int edge_count;
vector<edgeData<int>> edges;
vector<int> head;

void init(int n, int m) {
  edges = vector<edgeData<int>>(2 * m + 5);
  head = vector<int>(n + 5, -1);
  edge_count = 1;
}

void addEdge(int u, int v, int c = 0) {
  edges[edge_count].to = v;
  edges[edge_count].cost = c;
  edges[edge_count].nxt = head[u];
  head[u] = edge_count++;
}

void AddBiEdge(int u, int v, int c = 0) {
  addEdge(u, v, c);
  addEdge(v, u, c);
}

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    // cout << "Case #" << tc << ": ";
    Solve();
  }
  return 0;
}

47 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Graph Representation — Linked-List Adjacency

Faster cache-friendly alternative to vector> for dense graphs.

Setup

init(n, m);                  // n nodes, m edges (allocates 2*m+5 edge slots)
addEdge(u, v, c = 0);       // directed edge u→v with cost c
AddBiEdge(u, v, c = 0);     // undirected: both directions

Traversal Macro

adj_loop(u, v, e)
// v = neighbor of u, e = edge index
// edges[e].cost = edge weight

Example

init(n, m);
for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    AddBiEdge(u, v, w);
}
adj_loop(1, v, e) {
    cout << v << " " << edges[e].cost << "\n";
}