Algorithmica Notebook

Appearance

Graph and Tree Intro ​

Quick Revisit

  • USE WHEN: Problem mentions nodes/edges, cities/roads, or any connected-structure vocabulary
  • INVARIANT: A tree on n nodes has exactly n-1 edges and is connected; adjacency list stores edges in O(n+m) space
  • TIME: O(n+m) for DFS/BFS traversal | SPACE: O(n+m) adjacency list
  • CLASSIC BUG: Forgetting to add both directions for undirected edges (adj[u].push_back(v) AND adj[v].push_back(u))
  • PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Every graph problem on Codeforces assumes you already know 24 vocabulary words—this file teaches all of them with pictures.

Difficulty: Beginner | Prerequisites: Arrays & Strings

Contents ​

Intuition ​

Graph theory was born in 1736 when Leonhard Euler proved it was impossible to walk through Königsberg crossing each of its seven bridges exactly once—turning a city stroll into the first theorem of discrete mathematics. Every graph algorithm you learn descends from that single insight: structure, not geometry, determines what paths exist.

Think of a graph as a subway map. Stations are nodes, rail lines are edges. You don't care about the physical distance between stations; you care about which stations connect. That's topology, and it's the entire point.

The moment graphs "click" is when you realize that completely different real-world problems—social networks, road maps, task scheduling, tournament brackets—all reduce to the same dots-and-lines structure. Once you learn BFS on a graph, you can find shortest paths in all of those domains with zero extra work.

Mnemonic: When you see "cities," "people," "tasks," or "computers" connected by "roads," "friendships," "dependencies," or "cables"—you are looking at a graph.

The Problem Statement You Can't Read ​

You open CF 1092B. It says:

"Given a tree with n nodes, find the diameter."

You know arrays. You know loops. But what is a tree? What is a node? What is a diameter of a tree? The editorial says "root the tree and DFS." You don't know what rooting means. You don't know what DFS operates on.

Every graph problem assumes a shared vocabulary. Without it, you can't even parse the problem statement, let alone solve it. Array problems say "given an array of n integers"—you know exactly what that looks like in memory. Graph problems say "given a tree with n nodes and n−1 edges" and you stare blankly.

This isn't a skill gap. It's a vocabulary gap.

Graphs Are Just Dots and Lines ​

A graph is a collection of things (nodes) connected by relationships (edges)—and once you learn 24 vocabulary words, you can read any graph problem on Codeforces.

Think of a city map. Cities are dots. Roads between them are lines. That's it. A graph is a map: nodes are cities, edges are roads. Everything else—trees, paths, cycles, components—is just a pattern you can spot in that map.

The analogy is almost perfect. Where it breaks: real maps have geometry, where distances depend on physical space. Graphs are purely topological—only connections matter, not positions.

The 24-Word Visual Dictionary ​

Below is every term you need, with a picture, a one-line definition, and where you'll see it on Codeforces. Read this section like a picture book—the diagrams are the point.

Vertex (Node) ​

A thing. An object. A point. Draw it as a number.

text
    1       2       3       4       5

CF problems say: "n nodes," "n vertices," "n cities," "n people." All the same. Vertices are numbered 1 to n (or 0 to n−1).

Edge ​

A connection between two vertices. Draw it as a line.

text
    1 ----- 2

This edge connects vertex 1 to vertex 2. Written as the pair (1,2). CF problems say: "m edges," "m roads," "m friendships."

Undirected vs Directed ​

Undirected: the connection goes both ways. A road you can drive in either direction.

text
    1 ----- 2          "1 and 2 are connected"

Directed: the connection is one-way. A one-way street. Draw with an arrow.

text
    1 ----> 2          "1 points to 2" (but 2 does NOT point to 1)

A directed graph is called a digraph. CF problems almost always tell you: "undirected" or "directed." If they say "road between u and v" with no direction mentioned, assume undirected.

Weighted vs Unweighted ​

Unweighted: every edge is equal. Just a connection.

text
    1 ----- 2 ----- 3

Weighted: each edge has a number (cost, distance, time).

text
          5           3
    1 --------- 2 --------- 3

Edge (1,2) has weight 5. Edge (2,3) has weight 3.

CF wording: "the road between u and v has length w."

Degree ​

The number of edges touching a vertex.

text
    2       3
     \     /
      \   /
        1 ---------- 4
      /   \
     /     \
    5       6

Vertex 1 has degree 5: edges to {2, 3, 4, 5, 6}. Vertex 4 has degree 1: edge to {1} only.

For directed graphs, each vertex has:

  • In-degree: number of arrows pointing IN
  • Out-degree: number of arrows pointing OUT
text
        +----> 2
        |
    1 --+               in-degree(3) = 2
        |               out-degree(1) = 3
        +----> 3 <---- 4

Vertex 3: in-degree = 2 (arrows from 1 and 4), out-degree = 0. Vertex 1: in-degree = 0, out-degree = 3.

Handshaking lemma: Sum of all degrees = 2m (each edge contributes 2).

text
  Degree counting -- same graph undirected vs directed

  UNDIRECTED                  DIRECTED

  1 --- 2 --- 3               1 ---> 2 ---> 3
        |                           |
        4                           v
                                    4

  deg 1 = 1                   in 1 = 0  out 1 = 1
  deg 2 = 3                   in 2 = 1  out 2 = 2
  deg 3 = 1                   in 3 = 1  out 3 = 0
  deg 4 = 1                   in 4 = 1  out 4 = 0
  ----------                  ------------------
  sum = 6 = 2*3 edges         sum in = 3 = edges

Path ​

A sequence of vertices where each consecutive pair is connected by an edge, and no vertex repeats.

text
    1 --- 2 --- 3 --- 4 --- 5

Path from 1 to 5: 1→2→3→4→5. Length = 4 edges.

This is NOT a path (vertex 2 repeats):

text
    1 -> 2 -> 3 -> 2 -> 4       <-- not a path!

Walk ​

Like a path but can repeat vertices and edges. Less common in CF, but good to know the distinction.

text
    1 -> 2 -> 3 -> 2 -> 4       <-- valid walk, not a valid path

Cycle ​

A path that returns to its starting vertex.

text
    1 --- 2
    |     |
    |     |
    4 --- 3

Cycle: 1→2→3→4→1. Length = 4 edges.

A self-loop is a cycle of length 1: an edge from a vertex to itself. A graph with no cycles is called acyclic.

Cycle detection uses DFS back-edges → DFS and Tree DFS.

Connected ​

An undirected graph is connected if you can reach every vertex from every other vertex by following edges.

Connected:

text
    1 --- 2 --- 3
          |
          4 --- 5

Every vertex can reach every other. For example, 5→4→2→1.

NOT connected:

text
    1 --- 2       4 --- 5
          |
          3

Vertex 1 cannot reach vertex 4. No path exists between them.

Connected Component ​

A maximal connected subgraph. Informally: a connected "island" of vertices where you can't add any more vertices without breaking connectedness.

text
    Component 1       Component 2       Component 3
    +---------+       +---------+       +---+
    | 1 --- 2 |       | 4 --- 5 |       | 7 |
    |     |   |       |   |     |       +---+
    |     3   |       |   6     |
    +---------+       +---------+

Three components: {1,2,3}, {4,5,6}, {7}.

A connected graph has exactly 1 component. CF problems often ask: "Find the number of connected components." Find components with BFS/DFS → BFS | DFS.

Complete Graph ​

Every pair of vertices is connected. Notation: Kn.

K4 (4 vertices, 4⋅32=6 edges):

text
        1
       /|\
      / | \
     /  |  \
    2---+---3
     \  |  /
      \ | /
       \|/
        4

Kn has n(n−1)2 edges. K5 has 10 edges. K1000 has 499500 edges.

Bipartite Graph ​

You can split vertices into two groups so that every edge goes between groups, never within a group. Equivalently: 2-colorable.

text
    Group A     Group B
    +-----+     +-----+
    |  1  |-----|  4  |
    |     |--+  |     |
    +-----+  |  +-----+
             |
    +-----+  |  +-----+
    |  2  |--+--|  5  |
    |     |-----|     |
    +-----+     +-----+

    +-----+     +-----+
    |  3  |-----|  6  |
    +-----+     +-----+

All edges cross between Group A {1,2,3} and Group B {4,5,6}. No edge connects two vertices in the same group.

Test: A graph is bipartite ⟺ it has no odd-length cycle. Check via BFS 2-coloring → Bipartite Graphs.

DAG (Directed Acyclic Graph) ​

A directed graph with no cycles. Think: task dependencies.

text
    1 ----> 2 ----> 4
    |               ^
    |               |
    +-----> 3 ------+

Tasks: 1 must happen before 2 and 3. Both 2 and 3 must happen before 4. No way to follow arrows and return to where you started.

CF keyword: "topological sort," "dependencies," "ordering." → Topological Sort.

Adjacency ​

Two vertices are adjacent if an edge connects them. That's it.

text
    1 --- 2 --- 3

1 and 2 are adjacent. 2 and 3 are adjacent. 1 and 3 are NOT adjacent.

The neighbors of vertex 2 are {1,3}: all vertices adjacent to it.

Tree Vocabulary ​

Trees appear in a substantial fraction of CF problems rated 800–1400. Here's every word you need.

Tree ​

A connected, acyclic graph with exactly n−1 edges (for n vertices).

Any two of these three properties imply the third:

  • Connected
  • Acyclic (no cycles)
  • Exactly n−1 edges
text
        1
       / \
      2   3
     / \   \
    4   5   6
            |
            7

7 vertices, 6 edges. Connected. No cycles. It's a tree.

Root ​

Pick any vertex as the root. This turns an unrooted tree into a rooted tree—suddenly every edge has a direction (toward root = up, away = down).

Same tree, rooted at vertex 1:

text
            1           <-- root (depth 0)
           / \
          2   3         <-- depth 1
         / \   \
        4   5   6       <-- depth 2
                |
                7       <-- depth 3

Rooted at vertex 3 instead:

text
            3           <-- root
           / \
          1   6
         /     \
        2       7
       / \
      4   5

Same tree, completely different shape. The root is a choice, not a property. CF problems say "the tree is rooted at vertex 1" to fix this choice.

text
  Rooting transforms edges into parent-child directions

  BEFORE -- unrooted          AFTER -- rooted at 1

  1 --- 2                          1
  |     |                         / \
  |     |                        3   2
  3     4                            |
                                     4
  No parent or child          parent(2) = 1
  No depth defined            parent(3) = 1
  Edges are symmetric         parent(4) = 2
                              depth: 1=0  2=1  3=1  4=2

Parent and Child ​

In a rooted tree, for every non-root vertex v, the vertex one step closer to the root is its parent. The vertex one step away from the root is a child.

text
            1           <-- root
           / \
          2   3
         / \
        4   5
  • Parent of 2 = 1. Children of 2 = {4,5}.
  • Parent of 4 = 2. Children of 4 = {} (none).
  • Parent of 1 = none (root has no parent).

Every non-root vertex has exactly one parent.

Leaf ​

A vertex with no children. In the rooted tree above: 4, 5, 3.

Equivalently, in an unrooted tree: a vertex with degree 1.

text
            1
           / \
          2   3  <-- leaf (degree 1)
         / \
        4   5    <-- both leaves (degree 1)

CF problems: "process leaves first," "remove leaves one by one."

Sibling ​

Vertices that share the same parent.

text
            1
           / \
          2   3      <-- 2 and 3 are siblings (parent = 1)
         / \
        4   5        <-- 4 and 5 are siblings (parent = 2)

Depth ​

The distance from the root to this vertex (counting edges).

text
            1           depth 0
           / \
          2   3         depth 1
         / \   \
        4   5   6       depth 2
                |
                7       depth 3

depth(root)=0. depth(v)=depth(parent(v))+1.

Height ​

The longest path downward from a vertex to any leaf below it.

text
            1           height 3
           / \
          2   3         height 1, height 2
         / \   \
        4   5   6       height 0, height 0, height 1
                |
                7       height 0

height(leaf)=0. The height of the tree = height of root = 3.

Subtree ​

A vertex v and all of its descendants (children, grandchildren, ...).

text
            1
           / \
          2   3
         / \   \
        4   5   6
                |
                7

Subtree of vertex 2: {2,4,5}. Subtree of vertex 3: {3,6,7}. Subtree of vertex 1: the entire tree.

(The subtree diagrams above use the same 7-node tree from entry 15.)

Diameter ​

The longest path between any two vertices in the tree.

text
            1
           / \
          2   3
         / \   \
        4   5   6
                |
                7

Longest path: 4→2→1→3→6→7—length 5 edges.

The diameter is 5. Finding the diameter is a classic CF problem (two BFS/DFS from any node, then from the farthest node found). → BFS covers the two-BFS diameter trick.

Ancestor and Descendant ​

In a rooted tree, u is an ancestor of v if u lies on the path from v to the root. Equivalently, v is a descendant of u.

text
            1
           / \
          2   3
         / \
        4   5

Ancestors of 4: {2,1} (and 4 itself, depending on convention). Descendants of 2: {4,5} (and 2 itself).

"Is u an ancestor of v?" is one of the most common tree queries in CF.

Six diagrams showing different graph types. Refer back to these when reading CF problem statements.

The first is a simple undirected graph with 5 nodes and 6 edges:

text
        1 --------- 2
       / \         / |
      /   \       /  |
     /     \     /   |
    5       3 --+    |
     \           \   |
      \           \  |
       +-----------  4

Vertices: {1,2,3,4,5}. Edges: (1,2),(1,3),(1,5),(2,3),(2,4),(4,5). Vertex 2 has degree 3. Vertex 3 has degree 2.

A directed graph, with in/out degrees annotated in the table below:

text
           +----> 2 ----> 5
           |      ^
    1 -----+      |
           |      |
           +----> 3 ----> 4
text
    +--------+-----------+------------+
    | Vertex | In-degree | Out-degree |
    +--------+-----------+------------+
    |   1    |     0     |     2      |
    |   2    |     2     |     1      |
    |   3    |     1     |     2      |
    |   4    |     1     |     0      |
    |   5    |     1     |     0      |
    +--------+-----------+------------+

Sources (in-degree 0): {1}. Sinks (out-degree 0): {4,5}.

A rooted 7-node tree with all labels annotated—this diagram is the single most useful reference for the Tree Vocabulary section:

text
              1  <-------- root, depth=0, height=3
             / \
            /   \
           2     3  <---- depth=1, height(2)=1, height(3)=2
          / \     \
         /   \     \
        4     5     6  <- depth=2, leaf(4), leaf(5), height(6)=1
                    |
                    7  <- depth=3, leaf

    parent(7)=6, parent(6)=3, parent(3)=1
    children(2)={4,5}
    subtree(3)={3,6,7}
    diameter path: 4--2--1--3--6--7 (length 5)

A graph with two connected components—no edge crosses between the islands:

text
    Component A            Component B

    1 --- 2                5 --- 6
    |   / |                |     |
    |  /  |                |     |
    | /   |                |     |
    3 --- 4                7 --- 8

{1,2,3,4} is one component. {5,6,7,8} is another. No edge crosses between them. Number of components = 2.

The complete graph K4—every pair connected, every vertex has degree 3:

text
        1
       /|\
      / | \
     /  |  \
    2---+---4
     \  |  /
      \ | /
       \|/
        3

Every pair connected: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4). 6 edges total. Every vertex has degree 3.

A bipartite graph—no edge stays on the same side:

text
    Left        Right

    (1) ------- (4)
     |  \        |
     |   \       |
     |    \      |
    (2) ------- (5)
     |
     |
    (3) ------- (6)

Left: {1,2,3}. Right: {4,5,6}. Edges: (1,4),(1,5),(2,4),(2,5),(2,6),(3,6). No edge within the same side.

Formal Properties ​

With the visual dictionary complete, here are the key mathematical facts:

text
+--------------------------------------------------------------+
| GRAPH FACTS                                                  |
|                                                              |
| * Undirected graph: sum of degrees = 2 * |edges|            |
| * Tree with n vertices has exactly n-1 edges                 |
| * Tree: unique path between any two vertices                 |
| * K_n has n(n-1)/2 edges                                     |
| * Bipartite <=> no odd cycle                                 |
| * DAG <=> can be topologically sorted                        |
| * Connected graph with n vertices needs >= n-1 edges         |
| * Connected graph with n-1 edges and no cycle => tree        |
+--------------------------------------------------------------+

Equivalent definitions of a tree (any two imply all):

  • Connected + acyclic
  • Connected + exactly n−1 edges
  • Acyclic + exactly n−1 edges
  • Unique path between every pair of vertices

When to Reach for Graphs ​

Trigger phrases—scan for these in a problem statement. Any one of them signals a graph:

"Given n cities and m roads..." → undirected graph (vertices = cities, edges = roads)

"Given n people and friendship relations..." → undirected graph (vertices = people, edges = friendships)

"Given n tasks with dependencies..." → DAG (vertex = task, directed edge = "must come before")

"Given a tree with n nodes..." → tree (n−1 edges, connected, acyclic, guaranteed)

"Given a rooted tree..." → rooted tree (root specified, parent/child relationships defined)

"Given a directed graph, find if there's a cycle..." → cycle detection (look for back edges in DFS)

"Assign colors to vertices so no two adjacent share a color..." → graph coloring (2-coloring = bipartite check)

Common CF Patterns to Graph Vocabulary ​

When you read a CF problem, translate the story into graph vocabulary first. This table maps the 12 most common CF phrasings to the exact graph concept and the typical algorithm you'll reach for.

#CF Problem PatternGraph ConceptTypical Data Structure / Algorithm
1"cities connected by roads"undirected graphadjacency list, BFS/DFS
2"follow dependencies / prerequisites"DAGtopological sort (see Topo Sort)
3"social network friends"undirected graphconnected components via BFS/DFS
4"one-way streets"directed graphDFS, strongly connected components
5"minimum connections to link all cities"MSTKruskal (see MST) / Prim
6"shortest route between two cities"weighted graphDijkstra (see Dijkstra) / BFS (unweighted)
7"tournament bracket / elimination"tree (binary)DFS, simulate rounds
8"org chart / hierarchy / manager chain"rooted treeparent array, LCA queries
9"grid of cells, move up/down/left/right"implicit graph (grid)BFS on 4-directional neighbors
10"assign teams so no friends on same team"bipartite checkBFS 2-coloring (see Bipartite)
11"relay messages along a chain"path graphsimple traversal / DP
12"computer network, packets can loop"general graph with cyclesDFS cycle detection, visited array

Pattern Fingerprint: "connected components" → BFS/DFS + visited array. "shortest path, unweighted" → BFS. "shortest path, weighted" → Dijkstra. "dependencies" → topological sort. "assign 2 groups" → bipartite check.

Counter-examples—these look like graphs but aren't (yet):

"Given a grid..." → This IS a graph (cells = vertices, adjacent cells = edges), but the grid structure allows simpler representations. See BFS for grid-as-graph patterns.

"Given a string..." → Usually not a graph problem. But sometimes you build a graph from the string (suffix structures, character transitions).

What the Code Won't Teach You ​

You can read the definition of a tree but not verify one.

A valid tree on n nodes satisfies: exactly n−1 edges, connected, acyclic. In contests, you rarely verify—the problem guarantees it. But when debugging, knowing these three properties lets you sanity-check input and catch reading errors early.

text
  Three properties -- any two give TREE

  +-------------+
  | Connected   |--+
  +-------------+  |
                   +---> TREE
  +-------------+  |
  | Acyclic     |--+
  +-------------+  |
                   |
  +-------------+  |
  | n-1 edges   |--+
  +-------------+

Rooting a tree is a choice, not a property.

The same unrooted tree looks completely different when rooted at different vertices. Parent, child, depth, height, and subtree all depend on which root you pick. An unrooted tree has none of these concepts until you root it.

text
  Unrooted               Rooted at 1       Rooted at 3

   1 -- 2 -- 3                1                  3
        |                    / \                  |
        4                   2   3                 2
                            |                    / \
                            4                   1   4

Undirected adjacency list size is 2m, not m.

Each undirected edge (u,v) becomes two entries: v in adj[u] and u in adj[v]. When estimating memory or iterating all edges, remember the factor of 2. A tree on n nodes stores 2(n−1) adjacency entries, not n−1.

text
  Graph  1 --- 2 --- 3     m = 2 edges

  adj[1] | 2 |              1 entry
  adj[2] | 1 | 3 |          2 entries
  adj[3] | 2 |              1 entry
  --------                  --------
  total                     4 = 2*m

C++ STL for Graphs ​

Graphs have no dedicated STL container—you build them from the usual pieces.

ContainerUsage for GraphsExample
vector<vector<int>>Adjacency list (unweighted)adj[u].push_back(v)
vector<vector<pair<int,int>>>Adjacency list (weighted)adj[u].push_back({v, w})
vector<tuple<int,int,int>>Edge list (weighted)edges.push_back({w, u, v})
queue<int>BFS frontierq.push(start)
vector<bool>Visited trackingvisited[v] = true
vector<int>Parent/depth arraysparent[v] = u
text
  Adjacency list vs adjacency matrix for the same graph

  Graph:  1 --- 2
          |   / |
          |  /  |
          | /   |
          3 --- 4

  ADJACENCY LIST              ADJACENCY MATRIX
  +---+                          1  2  3  4
  | 1 |--> 2 -> 3             1| 0  1  1  0
  +---+                       2| 1  0  1  1
  | 2 |--> 1 -> 3 -> 4        3| 1  1  0  1
  +---+                       4| 0  1  1  0
  | 3 |--> 1 -> 2 -> 4
  +---+
  | 4 |--> 2 -> 3
  +---+

Graph Representation Comparison ​

Choosing the right representation is a 10-second decision that affects the rest of your solution. Use this table. (For a deep dive, see Graph Representation.)

Adjacency MatrixAdjacency ListEdge List
SpaceO(V2)O(V+E)O(E)
Add edgeO(1)O(1) amortizedO(1)
Check if edge (u,v) existsO(1)O(deg(u))O(E)
Iterate neighbors of vO(V)O(deg(v))O(E)
Remove edgeO(1)O(deg(u))O(E)
Memory for tree (E=V-1)O(V2)O(V)O(V)
Best use caseDense graphs, V≤5000Sparse graphs, most CPKruskal's MST, sorting by weight
CF frequencyRare~95% of problemsEdge-sorting problems

Rule of thumb: If V≤5000 and you need fast edge lookups, consider a matrix. Otherwise, always use adjacency list. Edge list is only for algorithms that process edges globally (Kruskal, Bellman-Ford).

text
  Decision tree for choosing representation

  Is V <= 5000 AND you need O(1) edge lookup?
        |                       |
       YES                     NO
        |                       |
        v                       v
  +----------------+    Is the algorithm edge-centric
  | Adj. Matrix    |    (Kruskal, Bellman-Ford)?
  +----------------+          |           |
                             YES         NO
                              |           |
                              v           v
                        +-----------+  +----------------+
                        | Edge List |  | Adj. List      |
                        +-----------+  | (DEFAULT)      |
                                       +----------------+

Implementation (Contest-Ready) ​

Minimal: Build an adjacency list and find degrees ​

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    // Invariant: after iteration i, adj stores the first i undirected edges
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // undirected
    }
    // degree of each vertex
    // Invariant: v visits vertices 1..n in order; each printed exactly once
    for (int v = 1; v <= n; v++)
        cout << "deg(" << v << ") = " << adj[v].size() << "\n";
}

Minimal: Read a rooted tree (parent array input) ​

Many CF problems give a tree as n−1 parent values: p2,p3,…,pn where pi is the parent of vertex i (vertex 1 is root).

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    vector<int> parent(n + 1, 0);
    // Invariant: after iteration i, children[] and parent[] are set for vertex i
    for (int i = 2; i <= n; i++) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    // find leaves (no children)
    for (int v = 1; v <= n; v++)
        if (children[v].empty())
            cout << v << " is a leaf\n";
}

Explained: Compute depth and height of a rooted tree ​

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        children[p].push_back(i);
    }

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

    // BFS from root to compute depth
    // depth[root] = 0, depth[child] = depth[parent] + 1
    queue<int> q;
    q.push(1);
    vector<int> order;  // topological order (BFS order = top-down)
    // Invariant: every dequeued vertex has its correct depth; order[] is BFS-sorted
    while (!q.empty()) {
        int v = q.front(); q.pop();
        order.push_back(v);
        for (int c : children[v]) {
            depth[c] = depth[v] + 1;
            q.push(c);
        }
    }

    // height computed bottom-up: process nodes in reverse BFS order
    // height[leaf] = 0, height[v] = max(height[child]) + 1
    reverse(order.begin(), order.end());
    // Invariant: when processing v, all descendants already have correct height
    for (int v : order) {
        height[v] = 0;
        for (int c : children[v])
            height[v] = max(height[v], height[c] + 1);
    }

    for (int v = 1; v <= n; v++)
        cout << "vertex " << v
             << ": depth=" << depth[v]
             << ", height=" << height[v] << "\n";
}

Adjacency List Construction Worked Example ​

Here is a step-by-step trace of building an adjacency list from scratch—the exact sequence you'd perform in a contest.

Problem statement: "Given n=5 cities and m=6 roads, read the roads and build a graph. Then print each city's neighbors."

Input format:

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

The graph looks like this:

text
        1
       / \
      /   \
     2 --- 3
     |     |
     |     |
     4 --- 5

Step-by-step construction (1-indexed):

After reading edge 1 2: adj[1]={2}, adj[2]={1} After reading edge 1 3: adj[1]={2,3}, adj[3]={1} After reading edge 2 3: adj[1]={2,3}, adj[2]={1,3}, adj[3]={1,2} After reading edge 2 4: adj[2]={1,3,4}, adj[4]={2} After reading edge 3 5: adj[3]={1,2,5}, adj[5]={3} After reading edge 4 5: adj[4]={2,5}, adj[5]={3,4}

Final adjacency list state:

text
  adj[1] --> | 2 | 3 |
  adj[2] --> | 1 | 3 | 4 |
  adj[3] --> | 1 | 2 | 5 |
  adj[4] --> | 2 | 5 |
  adj[5] --> | 3 | 4 |
  -----------------------
  Total entries: 12 = 2 * 6 edges

1-indexed version (most CF problems):

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

int main() {
    int n, m;
    cin >> n >> m;
    // n+1 slots so vertex indices 1..n are valid
    vector<vector<int>> adj(n + 1);
    // Invariant: after iteration i, adj contains the first i edges (both dirs)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // undirected: add both directions
    }
    // Print neighbors
    // Invariant: loop visits every vertex exactly once
    for (int v = 1; v <= n; v++) {
        cout << v << ":";
        for (int nb : adj[v]) cout << " " << nb;
        cout << "\n";
    }
}

Output:

text
1: 2 3
2: 1 3 4
3: 1 2 5
4: 2 5
5: 3 4

0-indexed version (some problems, grid graphs):

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

int main() {
    int n, m;
    cin >> n >> m;
    // n slots for vertices 0..n-1
    vector<vector<int>> adj(n);
    // Invariant: after iteration i, adj contains the first i edges (both dirs)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // convert 1-indexed input to 0-indexed
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // Invariant: loop visits every vertex 0..n-1 exactly once
    for (int v = 0; v < n; v++) {
        cout << v << ":";
        for (int nb : adj[v]) cout << " " << nb;
        cout << "\n";
    }
}

Key difference: 0-indexed uses adj(n) and u--; v--;. 1-indexed uses adj(n + 1) and reads vertices as-is. Pick one convention and stick with it for the entire contest. Mixing them is the fastest route to a wrong answer.

Operations Reference ​

Costs for the basic graph and tree operations you'll use most often:

OperationTimeSpace
Build adjacency list from m edgesO(n+m)O(n+m)
Check if u, v adjacent (adj. list)O(deg(u))--
Find degree of vertex vO(1)--
Find all neighbors of vO(deg(v))--
Count connected components (BFS/DFS)O(n+m)O(n)
Compute depth of all nodes (rooted tree)O(n)O(n)
Compute height of all nodesO(n)O(n)
Find tree diameter (two BFS)O(n)O(n)

Problem Patterns and Tricks ​

"Count Connected Components" ​

Read the graph, BFS/DFS from each unvisited vertex, count how many times you start a new traversal. That's the component count.

CF examples: CF 977E, CF 1294C.

"Is This Graph a Tree?" ​

Given n vertices and m edges: it's a tree if and only if m=n−1and the graph is connected (one component).

cpp
bool is_tree = (m == n - 1) && (num_components == 1);

CF examples: CF 115A, CF 580C.

"Find Leaves / Process from Leaves" ​

Leaves have degree 1. Many tree problems process leaves first, then remove them (like peeling an onion). This is essentially topological-sort thinking on trees.

CF examples: CF 1238C.

"Bipartite Check / 2-Coloring" ​

BFS with alternating colors. If you ever try to color a neighbor the same color as the current vertex, the graph is not bipartite.

CF examples: CF 862B, CF 1296E.

"Shortest Path in Unweighted Graph" ​

BFS from the source. The BFS level equals the shortest distance. This is the single most common use of BFS on Codeforces.

CF examples: CF 1037D, CF 1272D.

"Degree Counting" ​

Some problems just need you to count degrees: "How many vertices have odd degree?" or "find the vertex with maximum degree."

Handshaking lemma: the number of odd-degree vertices is always even.

CF examples: CF 1133E.

Rating Progression ​

What graph/tree skills are expected at each Codeforces rating level:

RatingWhat's ExpectedTypical Problem
CF 1200Build adjacency list, count components, identify trees, BFS for shortest path in unweighted graphCF 977E -- Cyclic Components
CF 1500DFS on trees, compute depth/height, bipartite check, topological sort on DAGCF 580C -- Kefa and Park (tree DFS with depth)
CF 1800Tree diameter, LCA basics, DP on trees, multi-source BFS, cycle detection in directed graphsCF 1092F -- Tree with Maximum Cost
CF 2100Euler paths, advanced tree decompositions, centroid decomposition, virtual trees, heavy-light decompositionCF 1153D -- Serval and Rooted Tree

"What Would You Do If...?" ​

Scenario 1: You read a problem about n computers connected by m cables. Some cables are one-directional. You need to find if all computers can reach computer 1.

Translation: Directed graph. Check if all vertices can reach vertex 1: reverse all edges, then BFS/DFS from vertex 1. If all vertices are visited, answer is YES.

Scenario 2: A problem gives n cities and n−1 roads, and asks for the two farthest cities.

Translation: This is a tree (n vertices, n-1 edges, connected). "Farthest cities" = diameter. Use two BFS: first from any node to find the farthest end, then from that end to find the true diameter.

Scenario 3: You're given n students and m pairs who refuse to be on the same team. Can you split them into exactly 2 teams?

Translation: Bipartite check. Build graph with "refuses" as edges. BFS 2-coloring. If any odd cycle exists, answer is NO. See Bipartite Graphs.

Contest Cheat Sheet ​

text
+--------------------------------------------------------------+
| GRAPH & TREE VOCABULARY CHEAT SHEET                          |
+--------------------------------------------------------------+
| Graph = vertices + edges                                     |
| Tree  = connected + acyclic + (n-1 edges)                    |
| Degree = # edges at vertex (in-deg + out-deg for directed)   |
| Path = no repeated vertices. Cycle = path back to start.     |
| Connected = one component. Bipartite = 2-colorable.          |
| DAG = directed + no cycles.                                  |
+--------------------------------------------------------------+
| ROOTED TREE QUICK FACTS:                                     |
| depth(root)=0, depth(v)=depth(parent)+1                      |
| height(leaf)=0, height(v)=max(height(child))+1               |
| diameter = longest path (find via 2x BFS/DFS)                |
| subtree(v) = v + all descendants                             |
+--------------------------------------------------------------+
| STORAGE:                                                     |
|   vector<vector<int>> adj(n+1);   // adjacency list          |
|   adj[u].push_back(v);            // add edge u->v           |
|   adj[v].push_back(u);            // (both dirs if undirected)|
+--------------------------------------------------------------+
| TREE INPUT (parent array):                                   |
|   for(int i=2;i<=n;i++) cin>>p[i], ch[p[i]].push_back(i);   |
+--------------------------------------------------------------+

"If I Had 5 Minutes" ​

Five-bullet speed reference—if you forget everything else, remember these:

  1. Graph = vertices + edges. Store with vector<vector<int>> adj(n+1).
  2. Undirected edge = TWO push_backs. adj[u].push_back(v); adj[v].push_back(u);
  3. Tree = connected graph with n-1 edges. No cycles, unique paths.
  4. BFS = shortest path in unweighted graph. queue<int> + visited[].
  5. Degree = adj[v].size(). Sum of all degrees = 2m (handshaking lemma).

Before You Code ​

Before writing a single line of graph code, answer these five questions:

  • [ ] Is it directed or undirected? (Determines whether you add one or two push_backs per edge)
  • [ ] Is it weighted or unweighted? (Determines vector<int> vs vector<pair<int,int>> for neighbors)
  • [ ] Is it a tree or general graph? (Trees have n-1 edges and no cycles—skip cycle handling if guaranteed)
  • [ ] What's the indexing? (1-indexed → adj(n+1). 0-indexed → adj(n). Check problem constraints)
  • [ ] What's the constraint size? (V≤5000 might allow O(V2) matrix; V≤2×105 requires adjacency list)

Gotchas and Debugging ​

These are the bugs that cost rounds. Every one below has burned thousands of contestants.

1-indexed vs 0-indexed. CF almost always uses 1-indexed vertices. Declare adj(n + 1), not adj(n). Off-by-one here causes segfaults or wrong answers on every single test case.

Forgetting both directions. For undirected graphs, you must add both adj[u].push_back(v) AND adj[v].push_back(u). Forgetting one direction is the #1 beginner graph bug. Your BFS won't reach half the graph.

Tree has n−1 edges, not m. When reading a tree, the number of edges is always n−1. Don't read m from input unless the problem says to—many tree problems only give n, and you read n−1 edges.

Root confusion. An unrooted tree has no root, parent, or depth until you pick a root. If the problem doesn't specify a root, you choose one (usually vertex 1). Don't assume a root exists in unrooted problems.

Diameter is edges, not vertices. The diameter of a path 4→2→1→3 is 3 (edges), not 4 (vertices). Some problems count vertices—read carefully.

Multi-edges and self-loops. CF problems usually state "simple graph" (no multi-edges, no self-loops). If not stated, your adjacency list might have duplicates. Check problem constraints.

Graph vs tree. A tree is a special graph. If the problem says "tree," you get all tree guarantees for free: connected, acyclic, n−1 edges, unique paths. Don't waste time checking what's guaranteed.

Mental Traps ​

Trap: "I read the definitions, so I know graphs."

Recognizing the word "bipartite" in a problem statement is not the same as translating it into a BFS 2-coloring. Vocabulary gives you parsing ability; only writing the code builds implementation ability. Write the code for every definition, not just the flashcard.

text
  WRONG                      RIGHT
  +---------------+          +---------------+
  | know the word |----+     | write the BFS |----+
  +---------------+    |     +---------------+    |
                       v                          v
  +---------------+          +---------------+
  | stuck         |          | solved        |
  +---------------+          +---------------+

Trap: "Depth and height are the same thing."

Depth is measured down from the root: depth(root) = 0. Height is measured up from the leaves: height(leaf) = 0. At the root of a perfectly balanced tree the values coincide, but at any internal node of an unbalanced tree they can differ wildly. Swapping them silently corrupts DP on trees.

text
  WRONG -- same values         RIGHT -- different values

       1  d0 h0                     1  d0 h2
      / \                          / \
     2   3  d1 h1                 2   3  d1 h0
                                 /
                                4  d2 h0

Trap: Visualizing every graph as a tree.

Trees are acyclic, connected, and have unique paths. General graphs can have cycles, multiple components, and many paths between two nodes. If you mentally picture a tree when the problem says "graph," you'll miss cycle handling, visited-array logic, and multi-component iteration.

text
  WRONG -- tree assumed       RIGHT -- graph has cycles

       1                      1 --- 2
      / \                     |   / |
     2   3                    |  /  |
    / \                       | /   |
   4   5                      3 --- 4

The Mistake That Teaches ​

The bug: You submit CF 977E (Cyclic Components). Your solution finds connected components using BFS, then checks if every vertex in each component has degree exactly 2. It passes the samples but gets Wrong Answer on test 3.

What you wrote:

cpp
// BFS to find components
// Invariant: all vertices in comp[] belong to the same component
vector<int> comp;
// ... BFS fills comp ...
bool is_cycle = true;
// Invariant: is_cycle remains true only if all checked vertices have deg 2
for (int v : comp)
    if (adj[v].size() != 2) is_cycle = false;

The hidden bug: You used adj(n) instead of adj(n + 1). Vertices are 1-indexed (1 to n), but your adjacency list only has slots 0 to n-1. Vertex n's edges are written to adj[n]—which is out of bounds. No segfault (vectors can silently corrupt), but edges involving vertex n go to the wrong place.

The fix: Change vector<vector<int>> adj(n) to adj(n + 1).

The lesson: When your solution passes samples but fails on larger tests, always check your indexing first. The one-off between 0-indexed allocation and 1-indexed input is the single most common graph bug in competitive programming. Add this to your mental checklist: "Did I allocate n+1?"

text
  The timeline of the bug

  +-------------------+     +------------------+     +------------------+
  | adj(n) allocated  | --> | adj[n] is OOB    | --> | silent corruption|
  | slots 0..n-1      |     | vertex n's edges |     | wrong component  |
  +-------------------+     | go nowhere       |     | wrong answer     |
                            +------------------+     +------------------+

Debug Exercises ​

Find the bug in each snippet. Answers are below—try first!

Bug 1: Undirected Graph—Missing Something?

cpp
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);
    // Where's the other direction?
}

Bug 2: Tree Reading—Wrong Loop Bound

cpp
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n; i++) {   // <-- how many edges does a tree have?
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

Bug 3: BFS—Infinite Loop

cpp
queue<int> q;
q.push(start);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int nb : adj[v]) {
        q.push(nb);   // <-- what's missing?
    }
}

Bug 4: Degree Computation—Wrong for Directed Graphs

cpp
// Directed graph: count in-degree of each vertex
vector<vector<int>> adj(n + 1);  // adj[u] stores outgoing neighbors
for (int v = 1; v <= n; v++)
    cout << "in-degree of " << v << " = " << adj[v].size() << "\n";
    // ^^ Is adj[v].size() the in-degree?
Answers (click to reveal)

Bug 1: Missing adj[v].push_back(u). For undirected graphs you must add both directions. BFS/DFS from vertex u would never discover v as a neighbor, and the graph appears disconnected.

Bug 2: A tree with n vertices has n−1 edges, not n. The loop should be for (int i = 0; i < n - 1; i++). Reading n edges tries to consume input that doesn't exist, causing undefined behavior or TLE.

Bug 3: Missing a visited[] check. Without if (!visited[nb]) before pushing, the BFS revisits vertices endlessly, causing an infinite loop (or MLE as the queue grows without bound).

cpp
vector<bool> visited(n + 1, false);
visited[start] = true;
queue<int> q;
q.push(start);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int nb : adj[v]) {
        if (!visited[nb]) {
            visited[nb] = true;
            q.push(nb);
        }
    }
}

Bug 4: adj[v].size() gives the out-degree, not the in-degree. For in-degree, you must count how many other vertices have v in their adjacency list—or maintain a separate in_deg[] array while reading edges: for each edge (u,v): in_deg[v]++.

When NOT to Use This ​

Graph vocabulary is powerful, but not everything is a graph problem:

  • Pure math/number theory: If the problem asks for GCD, prime factoring, or modular arithmetic with no connections between objects, don't force a graph model. See Math Toolkit.
  • Array manipulation: Prefix sums, sliding window, two pointers—these operate on sequential data. Building a graph from an array adds unnecessary complexity unless the problem explicitly involves connections. See Prefix Sums.
  • String problems: Pattern matching (KMP, Z-function) doesn't need graph structure unless the problem involves state machines or suffix automata.
  • Greedy on sorted data: If sorting + greedy solves it, a graph model is overkill. See Greedy.
  • Small constraints with brute force: If n≤20, bitmask enumeration or brute force is simpler than graph algorithms.

Red flag: If you're building a graph but every vertex has degree 0 or 1 and there are no meaningful traversals, you probably don't need a graph.

Self-Test ​

Before moving on to BFS/DFS, verify—without looking back—that you can:

  • [ ] State the three equivalent definitions of a tree and explain why any two imply the third
  • [ ] Write adjacency-list construction for an undirected graph with 1-indexed input—including correct allocation size and both-direction insertion
  • [ ] Given a rooted tree diagram, label every vertex with its depth and its height and explain why they differ
  • [ ] Explain why adj[v].size() gives degree in undirected graphs but only out-degree in directed graphs
  • [ ] State the handshaking lemma and use it to verify your adjacency list has the correct total size
  • [ ] Distinguish tree vs forest vs general graph—and state the edge count for each
  • [ ] Explain what "simple graph" means and what changes if the graph is not simple

Practice Problems ​

#ProblemSourceDifficultyKey Idea
1Bear and Big BrotherCF 791A800Not a graph—warm-up. Understand problem parsing first.
2King of ThievesCF 1197A800Simple pattern—builds reading skills.
3Mahmoud and Longest Uncommon SubsequenceCF 766A800String problem that teaches "read carefully."
4Cyclic ComponentsCF 977E1100Count connected components where every vertex has degree 2 (cycles).
5Two Teams ComposingCF 1335C1100Degree/counting on implicit graph structure.
6DFS OrderCF 580C1300Tree with root, parent, children—compute depth via DFS.
7Nearest Opposite ParityCF 1272D1300Build a directed graph from array, BFS for shortest path.
8Cat PartyCF 1163B21100Counting—trains reading problem statements with "graph-like" structure.

Start with problems 4 and 6—they directly use the vocabulary from this file.

Further Reading ​

What to Solve Next ​

You now have the full graph and tree vocabulary. Next steps:

  1. Traverse graphs—BFS for shortest unweighted paths, DFS for components and cycle detection: BFS | DFS and Tree DFS
  2. Apply graph techniques—bipartite checking, topological sort, shortest paths, and spanning trees: Bipartite | Topo Sort | Dijkstra | MST
  3. Bridge to the next chapter—see how graph foundations connect to DP and advanced topics: BRIDGE — Graph Foundations → DP
  4. Practice rated problems that exercise this vocabulary: Ladder 1100–1400
  5. Choose the right data structure for your next graph problem: Data Structure Selection Guide
  6. Explore tree-specific structures—segment trees, Fenwick trees, and more: Data Structures

Built for the climb from Codeforces 1100 to 2100.

Algorithmica Notebook