Graph Basics¶

In one sentence

A graph is a set of vertices joined by edges; store it as an adjacency list adj[u] = "the neighbours of \(u\)", which uses memory proportional to the number of edges instead of \(n^2\).

1. What problem does it solve?¶

Example — P1204 · Adjacency List (our judge, contest Graph Basics · D)

You are given an undirected simple graph with \(n\) vertices and \(m\) edges. For every vertex \(1, 2, \dots, n\), print its neighbours in increasing order on one line (an empty line if it has none).

Limits: \(n, m \le 2\cdot10^5\). Scoring: \(20\) points for \(n, m \le 1000\), \(30\) more for \(n, m \le 2\cdot10^4\), the last \(50\) for the full limits.

Input        Output
4 3
1 2
1 3
1 4          2 3 4
             1
             1
             1

5 2
1 2
3 4          2
             1
             4
             3
             (empty line)

The subtasks are a hint. An adjacency matrix is an \(n \times n\) table of 0/1. For \(n = 1000\) that is \(10^6\) cells, fine: 20 points. For \(n = 2\cdot10^5\) it is \(4\cdot10^{10}\) cells, around 40 GB. The matrix cannot even be created, and scanning a row to list neighbours costs \(O(n)\) per vertex, \(O(n^2)\) in total. The adjacency list stores only the \(2m\) neighbour entries that actually exist.

2. The math¶

2.1 Two ways to store the same graph¶

Sample 1 is a "star": vertex 1 in the middle, joined to 2, 3, 4.

graph LR
    1 --- 2
    1 --- 3
    1 --- 4

	adjacency matrix	adjacency list
picture for the star	`0 1 1 1` `1 0 0 0` `1 0 0 0` `1 0 0 0`	`adj[1] = {2, 3, 4}` `adj[2] = {1}` `adj[3] = {1}` `adj[4] = {1}`
numbers stored	\(n^2 = 16\)	\(2m = 6\)
is \((u, v)\) an edge?	\(O(1)\)	\(O(\deg u)\)
list the neighbours of \(u\)	\(O(n)\)	\(O(\deg u)\)

2.2 Why the list has exactly \(2m\) entries¶

Each undirected edge \((u, v)\) is pushed twice: adj[u].push_back(v) and adj[v].push_back(u). Since adj[u].size() is the degree of \(u\),

\[ \sum_{u=1}^{n} \deg(u) = \sum_{u=1}^{n} |\texttt{adj}[u]| = 2m . \]

This is the handshake lemma. It also says the total work of "for every vertex, loop over its neighbours" is \(O(n + m)\), not \(O(n^2)\).

2.3 The cost of sorting every list¶

Sorting adj[u] costs \(O(\deg u \log \deg u) \le O(\deg u \log m)\). Adding over all vertices and using the handshake lemma gives \(O(m \log m)\) in total.

2.4 Directed graphs¶

For a directed edge \(u \to v\) we push only adj[u].push_back(v). Each edge adds one to the out-degree of \(u\) and one to the in-degree of \(v\), so

\[ \sum_u \text{in}(u) = \sum_u \text{out}(u) = m . \]

That is exactly what the program from our 8 June lesson prints (the two sums always tie):

    vector<int> in(n + 1);
    vector<int> out(n + 1);

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

3. Lesson notes (Graph Theory, May)¶

1. Basic Definitions¶

1.0 Preliminaries¶

In set theory, we use \(\in\) to mean "is an element of". For example, \(v \in V\) means that the element \(v\) is in the set \(V\).
We usually use uppercase letters for sets and lowercase letters for elements.
A set is a collection of elements. This idea is different from the C++ STL data structure std::set.

1.1 Graph¶

A graph is written as \(G = (V, E)\).

\(V\) is the vertex set.
\(E\) is the edge set.

The graph contains vertices and edges. Vertices represent objects. Edges represent relationships between objects.

1.2 Vertex¶

A vertex is a node or a point in a graph. In real-world problems, a vertex can represent a city, a position, a room, a person, or a computer.

1.3 Edge¶

An edge connects two vertices. An edge between vertices \(u\) and \(v\) is written as \((u, v)\).

A directed edge \((u, v)\) gives a direction from \(u\) to \(v\).

An undirected edge \((u, v)\) connects \(u\) and \(v\) in both directions.

1.4 Weighted Edge¶

A weighted edge has a value on it. The value is called the weight.

In real-world problems, a weight can represent distance, cost, time, or capacity.

For example, an edge from city \(u\) to city \(v\) with weight \(10\) can mean that the distance from \(u\) to \(v\) is \(10\).

1.5 Degree¶

Definition:

The degree of a vertex \(u\) is the number of edges connected to \(u\).

We write it as \(\deg(u)\).

For an undirected graph, the degree of vertex \(u\) is the number of neighbors of \(u\).

Example:

If vertex \(u\) is connected to \(3\) other vertices, then \(\deg(u) = 3\).

For a directed graph, each vertex has two kinds of degree.

The in-degree is the number of edges entering the vertex.
The out-degree is the number of edges leaving the vertex.

2. Adjacency Matrix and Adjacency List¶

2.0 Preliminaries¶

A matrix is a rectangular table of numbers.
We usually use uppercase letters for matrices and lowercase letters for the values inside them.
\(a_{i,j}\) is the value in the \(i\)-th row and the \(j\)-th column of matrix \(A\).

2.1 Adjacency Matrix¶

An adjacency matrix uses a matrix to store the edges of a graph.

For an unweighted graph, we define matrix \(A\) as:

\[ a_{i,j} = \begin{cases} 1, & \text{if there is an edge from } i \text{ to } j \\ 0, & \text{if the edge is absent} \end{cases} \]

For an undirected graph, the edge \((u, v)\) gives both \(a_{u,v} = 1\) and \(a_{v,u} = 1\).

Code:

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

vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));

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

    adj[u][v] = 1;
    adj[v][u] = 1;
}

The matrix contains \(n^2\) values, so the memory complexity is \(O(n^2)\).

Checking whether edge \((u, v)\) exists takes \(O(1)\) time:

if (adj[u][v] == 1) {
    cout << "edge exists\n";
}

2.2 Neighborhood with an Adjacency Matrix¶

The neighbors of vertex \(u\) are the vertices connected to \(u\).

To find all neighbors of vertex \(u\), we scan the row adj[u].

vector<int> neighbors(int u, const vector<vector<int>>& adj, int n) {
    vector<int> res;

    for (int v = 1; v <= n; v++) {
        if (adj[u][v] == 1) {
            res.push_back(v);
        }
    }

    return res;
}

This takes \(O(n)\) time.

2.3 Adjacency List¶

An adjacency list stores the neighbors of each vertex.

For each vertex \(u\), adj[u] is a list of vertices connected to \(u\).

Code for an undirected graph:

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

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);
}

Code for a directed graph:

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

vector<vector<int>> adj(n + 1);

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

    adj[u].push_back(v);
}

The adjacency list stores one value for each directed edge. For an undirected graph, each edge is stored twice.

The memory complexity is \(O(n + m)\).

For an undirected graph with \(m\) edges, the adjacency list stores \(2m\) numbers in total.

int total_numbers = 0;

for (int i = 1; i <= n; i++) {
    total_numbers += adj[i].size();
}

After the loop, total_numbers is equal to \(2m\).

2.4 Neighborhood with an Adjacency List¶

With an adjacency list, the neighbors of vertex \(u\) are stored directly in adj[u].

for (int v : adj[u]) {
    cout << v << ' ';
}

This takes \(O(\deg(u))\) time, where \(\deg(u)\) is the degree of vertex \(u\).

2.5 Degree with an Adjacency List¶

The degree of vertex \(u\) is the size of its neighborhood.

In code, this value is adj[u].size().

int u = 5;
int degree = adj[u].size();

For an undirected graph, each edge increases the total degree by \(2\).

The sum of degrees over all vertices is \(2m\).

\[ \sum_{u=1}^{n}\deg(u) = 2m \]

Code:

int degree_sum = 0;

for (int u = 1; u <= n; u++) {
    degree_sum += adj[u].size();
}

After the loop, degree_sum is equal to \(2m\).

2.6 Matrix and List Comparison¶

An adjacency matrix is useful when the program checks edge existence many times.

An adjacency list is useful when the graph has many vertices and relatively few edges.

Representation	Memory	Check edge \((u, v)\)	List neighbors of \(u\)
Adjacency matrix	\(O(n^2)\)	\(O(1)\)	\(O(n)\)
Adjacency list	\(O(n + m)\)	\(O(\deg(u))\)	\(O(\deg(u))\)

3. Common Input Format¶

Many graph problems use this input format:

n m
u1 v1
u2 v2
...
um vm

n is the number of vertices.
m is the number of edges.
Each pair ui vi gives one edge.

Example:

This graph has \(5\) vertices and \(4\) edges.

The edges are \((1, 2)\), \((1, 3)\), \((2, 4)\), and \((3, 5)\).

4. Basic Input Template¶

This is a common input template for an undirected graph.

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

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

    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);
    }

    return 0;
}

After this code runs, adj[u] stores the vertices connected to vertex u.

4. Worked solution — Adjacency List¶

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;

    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 (int u = 1; u <= n; u++) {
        sort(adj[u].begin(), adj[u].end());
        for (int i = 0; i < (int) adj[u].size(); i++) {
            if (i > 0) {
                cout << " ";
            }
            cout << adj[u][i];
        }
        cout << "\n";
    }
}

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

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. Reading a graph problem¶

The statement says…	It means
"\(n\) cities and \(m\) roads", "\(n\) people, \(m\) friendships"	vertices and edges
"the road from \(u\) to \(v\) can be used in both directions"	undirected: push both ways
"one-way", "\(u\) points to \(v\)", "\(u\) follows \(v\)"	directed: push once
"no two roads connect the same pair", "no road from a city to itself"	simple graph: no duplicates, no self-loops
\(n \le 1000\)	a matrix is allowed
\(n \le 2\cdot10^5\)	adjacency list

6. Common mistakes¶

Forgetting the second push_back

For an undirected edge both endpoints must list each other, otherwise vertex 2 in sample 1 has no neighbours.

vector<vector<int>> adj(n) with vertices \(1 \dots n\)

adj[n] is out of range. Use size n + 1.

adj[u].size() - 1 when \(u\) has no neighbours

size() is unsigned; 0 - 1 wraps around. See Integer Types & Overflow.

endl after every line

With \(2\cdot10^5\) output lines, endl flushes \(2\cdot10^5\) times and can time out. Use "\n".

7. Practice¶

Problem	Where	Idea
P1201 · Vertex Degrees	OJ Graph Basics · A	`deg[u]++`, `deg[v]++` per edge; no list needed
P1202 · In and Out	OJ Graph Basics · B	`out[u]++`, `in[v]++` (§2.4)
P1203 · Most Connected	OJ Graph Basics · C	largest degree, ties to the smaller index
P1204 · Adjacency List	OJ Graph Basics · D	this page
1020B · Badge	8-Graph · A	follow the single outgoing edge until a repeat
1829F · Forever Winter	8-Graph · B	recover \(x\) and \(y\) from the degrees
217A · Ice Skating	8-Graph · C	build the graph yourself, count components
AIO 2019 · Evading Capture	AIO 2019 Q5	adjacency list + BFS with parity states

Credits & licenses

§3 is our Graph Theory handout from May (lessons of 13 and 27 May), unchanged apart from heading levels. The in/out-degree snippet is quoted unchanged from the 8 June lesson file.
The OJ problems were written for these lessons. Example, comparison table, handshake argument, worked solution and mistakes are ours.