Chapter 5.1: Introduction to Graphs

A graph is one of the most versatile mathematical structures ever invented. It models relationships between things — roads between cities, friendships between people, connections between web pages. In USACO, graphs represent mazes, networks, and relationships between cows.

5.1.1 What Is a Graph?

A graph consists of:

• Vertices (also called nodes): the "things" (cities, cows, cells)
• Edges: the connections between them (roads, friendships)

Visual: Graph Basics Reference

This reference diagram shows the key graph terminology — vertices, edges, directed vs undirected, weighted edges, and common graph properties — all in one view.

Types of Graphs

Most USACO Bronze/Silver problems use unweighted, undirected graphs or simple grids.

5.1.2 Graph Representation

The most important decision when coding a graph algorithm is how to store the graph.

Visual: Graph Structure and Adjacency List

The left side shows an undirected graph with 5 nodes and their edges. The right side shows the adjacency list — for each node, a list of its neighbors. This representation uses O(V + E) space, which is optimal for sparse graphs typical in USACO problems.

Adjacency List (USE THIS)

Store each vertex's neighbors as a list. This is the standard in competitive programming.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;  // n vertices, m edges
    cin >> n >> m;

    // adj[u] = list of vertices connected to u
    vector<vector<int>> adj(n + 1);  // 1-indexed: vertices 1..n

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // edge u → v
        adj[v].push_back(u);  // edge v → u (undirected: add both directions)
    }

    // Print adjacency list
    for (int u = 1; u <= n; u++) {
        cout << u << " -> ";
        for (int v : adj[u]) cout << v << " ";
        cout << "\n";
    }

    return 0;
}

Input:

6 6
1 2
1 3
2 4
3 5
4 6
5 6

Output:

1 -> 2 3
2 -> 1 4
3 -> 1 5
4 -> 2 6
5 -> 3 6
6 -> 4 5

Space complexity: O(V + E). For V = 10^5 and E = 2×10^5, this is fine.

Adjacency Matrix (When to Use)

A 2D array where adj[u][v] = 1 if there's an edge from u to v.

bool adj[1001][1001] = {};  // global, zero-initialized

// Add edge u-v
adj[u][v] = true;
adj[v][u] = true;  // undirected

// Check if edge exists: O(1)
if (adj[u][v]) { ... }

Space complexity: O(V²). For V = 10^5, that's 10^10 bytes — way too much! Only use for V ≤ 1000.

When to Use Which

Default in competitive programming: Always use adjacency list unless V is very small.

5.1.3 Reading Graph Input

USACO graphs come in several formats. Here are the patterns:

Standard: Edge List

5 4        ← n vertices, m edges
1 2        ← edge between 1 and 2
2 3
3 4
4 5

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

Tree: Parent Array

5          ← n nodes
2 3 1 1    ← parent[2]=2, parent[3]=3, parent[4]=1, parent[5]=1 (node 1 is root)

int n;
cin >> n;
vector<vector<int>> children(n + 1);
for (int i = 2; i <= n; i++) {
    int parent;
    cin >> parent;
    children[parent].push_back(i);  // parent → child edge
}

Grid Graph

A grid where cells are nodes; edges connect adjacent cells (up/down/left/right):

4 4        ← rows × columns
....
.##.
....
....

int R, C;
cin >> R >> C;
vector<string> grid(R);
for (int r = 0; r < R; r++) cin >> grid[r];

// To iterate over neighbors of cell (r, c):
int dr[] = {-1, 1, 0, 0};  // row offsets for up/down/left/right
int dc[] = {0, 0, -1, 1};  // col offsets

for (int d = 0; d < 4; d++) {
    int nr = r + dr[d];  // neighbor row
    int nc = c + dc[d];  // neighbor col
    if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
        // (nr, nc) is a valid neighbor
    }
}

5.1.4 Trees vs. Graphs

A tree is a special type of graph with these properties:

• N nodes and exactly N-1 edges
• Connected (every node reachable from every other)

Visual: Rooted Tree Structure

A rooted tree has a designated root node at depth 0. Each node has a parent (except the root) and zero or more children. Leaf nodes have no children. This structure naturally represents hierarchies and enables efficient tree DP algorithms.

• No cycles (acyclic)

Trees appear constantly in USACO — they represent hierarchies, family trees, and many other structures.

        1          ← root
       / \
      2   3
     / \   \
    4   5   6

Key tree vocabulary:

• Root: The topmost node (usually node 1)
• Parent: The node directly above in the hierarchy
• Children: Nodes directly below
• Leaf: A node with no children
• Depth: Distance from the root (root has depth 0)
• Height: Length of the longest path from a node to a leaf

Representing a Rooted Tree

vector<vector<int>> children(n + 1);  // children[u] = list of u's children
int parent[n + 1];

// Read tree as undirected graph, then root it with DFS
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Root at node 1 using DFS
fill(parent + 1, parent + n + 1, 0);
function<void(int, int)> root_tree = [&](int u, int par) {
    parent[u] = par;
    for (int v : adj[u]) {
        if (v != par) {
            children[u].push_back(v);
            root_tree(v, u);  // recursive DFS
        }
    }
};
root_tree(1, 0);

5.1.5 Weighted Graphs

For weighted graphs (edges with costs), store the weight alongside each neighbor:

vector<vector<pair<int,int>>> adj(n + 1);
// adj[u] = list of {v, weight} pairs

// Add weighted edge u-v with weight w
adj[u].push_back({v, w});
adj[v].push_back({u, w});

// Iterate neighbors with weights
for (auto [v, w] : adj[u]) {
    cout << "Edge " << u << "-" << v << " weight " << w << "\n";
}

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Why use vector<vector<int>> for adjacency list instead of linked lists?

A: C++ vector uses contiguous memory, is cache-friendly, and is much faster than linked lists. In contests, list is almost never used; vector<vector<int>> is the standard approach.

Q2: Should graph vertices be 0-indexed or 1-indexed?

A: USACO problems are usually 1-indexed. Recommend declaring adjacency list with size n+1: vector<vector<int>> adj(n+1). This wastes index 0 but makes code clearer and less error-prone.

Q3: What is the only difference between directed and undirected graphs?

A: When reading edges, undirected graphs add two (u→v and v→u), directed graphs add only one (u→v). The subsequent BFS/DFS code is identical.

Q4: Does a grid graph need an explicit adjacency list?

A: No! Grid graph "neighbors" can be computed implicitly via direction arrays dr[]/dc[], no need to store an adjacency list—saves memory and is cleaner.

🔗 Connections to Later Chapters

• Chapter 5.2 (BFS & DFS) runs on the adjacency list built in this chapter—this chapter is a prerequisite for Chapter 5.2
• Chapter 5.3 (Trees & DSU) uses this chapter's tree representation and adds Union-Find
• Graph traversal from Chapters 5.1–5.2 is the foundation for "Tree DP" and "DP on DAG" in Chapters 6.1–6.3 (DP)
• Grid graph representation is used throughout the book—BFS shortest path, Flood Fill, grid DP, etc.

Practice Problems

Problem 5.1.1 — Degree Count Read an undirected graph with N vertices and M edges. Print the degree (number of edges) of each vertex.

Problem 5.1.2 — Is It a Tree? Read a connected graph. Determine if it's a tree (exactly N-1 edges and no cycles).

Problem 5.1.3 — Reachability Read a directed graph and two vertices S and T. Print "YES" if T is reachable from S following directed edges, "NO" otherwise. (You'll need DFS from Chapter 5.2 to fully solve this, but you can set it up now)

Problem 5.1.4 — Leaf Count Read a rooted tree. Count how many nodes are leaves (have no children).

Problem 5.1.5 — Grid to Graph Read an N×M grid. Cells with '.' are passable; '#' are walls. Print the number of edges in the implicit graph (connect adjacent '.' cells).

Visual: Graph Adjacency List

The left side shows a 5-node weighted graph visually. The right side shows the corresponding adjacency list in C++: vector<pair<int,int>> adj[] where each entry is a {neighbor, weight} pair. This is the standard representation for most USACO graph problems.