Chapter 5.1: Introduction to Graphs

📝 Before You Continue: You should be comfortable with arrays, vectors, and basic C++ (Chapters 2–4). Familiarity with struct (Chapter 2.4) and STL containers like vector and pair (Chapter 3.1) will be helpful.

Think of a graph as a map: cities are nodes, roads between them are edges. Graphs are the most versatile data structure in competitive programming — they model friendships between people, dependencies between tasks, cells in a maze, and much more. In USACO, nearly every problem at Silver level and above involves graphs in some form.

This chapter teaches you how to think in graphs and, more importantly, how to store them in code. By the end, you'll be able to read any USACO graph input and choose the right representation without hesitation.

5.1.1 What Is a Graph?

A graph G = (V, E) consists of two sets:

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

We write |V| = N for the number of vertices and |E| = M for the number of edges.

How Do We Store a Graph?

Before diving into terminology, let's get a quick preview of how graphs are stored in code. There are two main approaches (we'll cover them in detail in §5.1.2):

Adjacency List — For each vertex, store a list of its neighbors. This is the most common representation:

adj[0] = {1, 2}        ← node 0 connects to 1 and 2
adj[1] = {0, 2, 3}     ← node 1 connects to 0, 2, and 3
adj[2] = {0, 1, 4}     ← node 2 connects to 0, 1, and 4
adj[3] = {1, 4}         ← node 3 connects to 1 and 4
adj[4] = {2, 3}         ← node 4 connects to 2 and 3

Adjacency Matrix — Use a V×V grid where adj[u][v] = 1 means "edge exists between u and v":

adj:   0  1  2  3  4
  0  [ 0  1  1  0  0 ]     ← node 0 connects to 1 and 2
  1  [ 1  0  1  1  0 ]     ← node 1 connects to 0, 2, and 3
  2  [ 1  1  0  0  1 ]     ← node 2 connects to 0, 1, and 4
  3  [ 0  1  0  0  1 ]     ← node 3 connects to 1 and 4
  4  [ 0  0  1  1  0 ]     ← node 4 connects to 2 and 3

💡 Quick comparison: Adjacency list uses less memory and is faster for traversal — use it 95% of the time. Adjacency matrix gives O(1) edge lookup — useful when V is small (≤ 1500) or for algorithms like Floyd-Warshall.

The following two diagrams show the same 5-node graph stored as an adjacency list and an adjacency matrix:

In the matrix, green 1 = edge exists, gray 0 = no edge. The shaded diagonal cells are always 0 (no self-loops). Notice the matrix is symmetric — because the graph is undirected.

Key Terminology

You don't need to memorize all of these right now — just skim them and come back as needed.

Handshaking Lemma

The sum of all vertex degrees equals 2M (twice the number of edges).

Proof: each edge (u, v) contributes exactly +1 to deg(u) and +1 to deg(v).

Implication: The number of odd-degree vertices in any graph is always even. This can immediately rule out impossible cases in problems.

Types of Graphs

Graphs come in several flavors. Here are the ones you'll encounter most often:

USACO reality: Bronze/Silver mostly uses unweighted undirected graphs and grid graphs. Weighted graphs appear in Silver shortest paths. Trees appear at all levels. Gold introduces DAGs, directed graphs, and dense graphs.

5.1.2 Graph Representation

Now that you know what a graph is, the next question is: how do you store it in code? This is the most critical coding decision for graph problems. Three main representations exist, each with different trade-offs. Choosing wrongly leads to TLE or MLE.

Representation 1: Adjacency List — The Default Choice

For each vertex, store a list of its neighbors. This is the go-to representation for 95% of USACO problems.

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

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

    int n, m;          // n vertices (1..n), m edges
    cin >> n >> m;

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

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

    // Traverse all neighbors of vertex u: O(deg(u)) — optimal
    for (int u = 1; u <= n; u++) {
        cout << u << " -> ";
        for (int v : adj[u]) cout << v << " ";
        cout << "\n";
    }

    return 0;
}

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

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

Properties:

• Space: O(V + E) — optimal. For V = 10^5, E = 2×10^5 easily fits in 256 MB.
• Iterate neighbors: O(deg(u)) — only visits actual neighbors, never wasted work.
• Check edge (u, v): O(deg(u)) — must scan neighbor list. (This is the weakness.)
• Cache performance: vector uses contiguous memory → 5–10× faster than linked lists.

Why not std::list? Linked lists cause cache misses on every traversal step. In competitive programming, vector is always the right choice.

Representation 2: Adjacency Matrix

An adjacency matrix represents a graph as a 2D array where entry adj[u][v] answers: "Does an edge from u to v exist?"

The Core Idea

For a graph with V vertices, allocate a V×V boolean table. Row u, column v → does edge u→v exist?

Consider a graph with 4 nodes and edges 1–2, 1–3, 2–3, 3–4. Its adjacency matrix looks like:

adj:   1  2  3  4
  1  [ 0  1  1  0 ]     ← node 1 connects to 2 and 3
  2  [ 1  0  1  0 ]     ← node 2 connects to 1 and 3
  3  [ 1  1  0  1 ]     ← node 3 connects to 1, 2, and 4
  4  [ 0  0  1  0 ]     ← node 4 connects to 3 only

Key property: For undirected graphs, the matrix is always symmetric — adj[u][v] == adj[v][u]. The diagonal is always 0 (no self-loops in simple graphs).

Code — Undirected Unweighted Graph

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

const int MAXV = 1001;

// CRITICAL: declare as GLOBAL variable!
// A local bool[1001][1001] on the stack is ~1 MB → stack overflow crash.
// Global variables are stored in BSS segment and auto zero-initialized.
bool adj[MAXV][MAXV];

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

    int n, m;
    cin >> n >> m;     // n vertices (1..n), m edges

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = true;   // undirected: set BOTH directions
        adj[v][u] = true;   // adj[u][v] == adj[v][u] always
    }

    // === The killer feature: O(1) edge existence check ===
    if (adj[2][3]) {
        cout << "Edge 2-3 exists\n";
    }

    // Iterate all neighbors of vertex u: O(V) — must scan full row
    int u = 1;
    cout << "Neighbors of " << u << ": ";
    for (int v = 1; v <= n; v++) {
        if (adj[u][v]) cout << v << " ";
    }
    cout << "\n";

    return 0;
}

⚠️ Critical: Always use global arrays. A local bool adj[1001][1001] consumes ~1 MB of stack space — this will typically crash. Global arrays live in BSS/data segment with no stack size limit and are zero-initialized automatically.

Directed and Weighted Variants

The adjacency matrix adapts easily to directed and weighted graphs:

// --- Directed graph: only set ONE direction ---
cin >> u >> v;
adj[u][v] = true;    // u → v only; do NOT set adj[v][u]
// The matrix is no longer symmetric

// --- Weighted graph: replace bool with int, use INF sentinel ---
const int MAXV = 501;
const int INF  = 1e9;   // "no edge" / "infinite distance"
int dist[MAXV][MAXV];   // global!

void initMatrix(int n) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = (i == j) ? 0 : INF;
}

void addEdge(int u, int v, int w) {
    dist[u][v] = w;
    dist[v][u] = w;   // omit for directed graphs
}

Why INF = 1e9? Floyd-Warshall adds dist[i][k] + dist[k][j]. Using 1e9 keeps the sum within 32-bit int range; 2e9 would overflow.

This weighted matrix is the exact starting point for Floyd-Warshall (all-pairs shortest paths, Chapter 5.4):

// Floyd-Warshall: O(V^3)
void floydWarshall(int n) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Space: When Can You Use Adjacency Matrix?

V =   100  →  bool[100][100]     =    10 KB   ✅ trivial
V =   500  →  bool[500][500]     =   250 KB   ✅ fine
V =  1000  →  bool[1000][1000]   =     1 MB   ✅ fine
V =  1500  →  bool[1500][1500]   =  2.25 MB   ✅ fine
V =  3000  →  bool[3000][3000]   =     9 MB   ⚠️ borderline (256 MB limit)
V = 10000  →  bool[10k][10k]     =   100 MB   ❌ exceeds typical limit
V = 10^5   →  bool[10^5][10^5]   =    10 GB   ❌ impossible

Rule of thumb: Safe when V ≤ ~1500. For V > 2000, switch to adjacency list.

Complete Comparison

Representation 3: Edge List

Store the graph as a plain array of (u, v) or (u, v, w) tuples. Minimal structure.

// Edge struct for weighted graph
struct Edge {
    int u, v, w;
    // For sorting by weight (ascending):
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<Edge> edges;

// Read input:
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edges.push_back({u, v, w});
}

// Sort by weight — needed for Kruskal's MST:
sort(edges.begin(), edges.end());

// Or sort by source vertex:
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
    return a.u < b.u;
});

When to use edge list:

When NOT to use edge list:

• BFS/DFS: no per-vertex neighbor lookup
• Checking "does edge (u, v) exist?": O(M) scan

Tip: For problems needing both BFS and Kruskal, maintain both an edge list and an adjacency list simultaneously. The memory overhead is small.

How to Choose a Representation

The decision is simpler than it looks:

Is V ≤ 1500?
├── YES → Do you need O(1) edge check or Floyd-Warshall?
│         ├── YES → Adjacency Matrix
│         └── NO  → Adjacency List
└── NO  → Adjacency List (always)
            └── Also need Kruskal? → Add an Edge List too

Default rule: Start with adjacency list. Switch to matrix only when V is explicitly small (≤ 1500) or Floyd-Warshall is required.

5.1.3 Reading Graph Input

You know the data structures — now let's connect them to real USACO input. Recognizing the input pattern immediately saves crucial contest time. Here are the five formats you'll encounter:

Format 1: Standard Edge List (Most Common)

5 4        <- n vertices, m edges (first line)
1 2        <- each subsequent line: one undirected edge
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);   // omit for directed graphs
}

Format 2: Weighted Edge List

4 5        <- n vertices, m edges
1 2 10     <- edge 1-2, weight 10
1 3 5      <- edge 1-3, weight 5
2 3 3
2 4 8
3 4 2

int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);
// adj[u] = list of {neighbor, weight} pairs
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});  // undirected weighted
}

// C++17 structured bindings for iteration:
for (auto& [v, w] : adj[1]) {
    cout << "1 -> " << v << " (weight " << w << ")\n";
}

Format 3: Tree via Parent Array

5          <- n nodes; root is always node 1
2 3 1 1    <- parent[2]=2, parent[3]=3, parent[4]=1, parent[5]=1

In this common USACO format, n−1 parents are given for nodes 2..n:

int n;
cin >> n;
vector<vector<int>> children(n + 1);
vector<int> par(n + 1, 0);
for (int i = 2; i <= n; i++) {
    cin >> par[i];
    children[par[i]].push_back(i);   // directed: parent -> child
}
// par[1] = 0 (root has no parent)

Format 4: Grid Graph (Very Common in USACO Bronze/Silver)

4 5        <- R rows, C columns
.....      <- '.' = passable, '#' = wall/obstacle
.##..
.....
.....

Cells are nodes; adjacent passable cells share an edge. No explicit adjacency list needed — use direction delta arrays:

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

// 4-directional: up, down, left, right
const int dr[] = {-1,  1,  0, 0};
const int dc[] = { 0,  0, -1, 1};

// At any cell (r, c), iterate valid passable neighbors:
auto neighbors = [&](int r, int c) {
    vector<pair<int,int>> result;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != '#') {
            result.push_back({nr, nc});
        }
    }
    return result;
};

Pro tip: For 8-directional movement (including diagonals), use:

const int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1};
const int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1};

Flattening cells to a single integer (useful for visited arrays):

// Cell (r, c) → integer ID: r * C + c  (0-indexed)
int cellId(int r, int c, int C) { return r * C + c; }
// Back: id → (id / C, id % C)

Format 5: Edge List with Self-Loops and Multi-Edges

Some problems include self-loops (u = v) or multi-edges (multiple edges between the same pair). Handle explicitly:

// Skip self-loops (if not meaningful in the problem):
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u == v) continue;    // self-loop: skip
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Deduplicate multi-edges (build simple graph only):
set<pair<int,int>> seen;
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);         // normalize: always u < v
    if (seen.insert({u, v}).second) {
        // .second = true means newly inserted (not duplicate)
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

5.1.4 Trees — A Special Type of Graph

Trees are the most important special case of graphs. They appear at every USACO level, from Bronze to Platinum. If you master trees, you've mastered half of graph theory.

A tree is a graph satisfying all of the following (they are equivalent conditions):

1. Connected with exactly N − 1 edges
2. Connected and acyclic (contains no cycle)
3. Any two vertices are connected by exactly one simple path
4. Minimally connected: removing any edge disconnects it

Why These Are Equivalent

Proof sketch (informal):

• Connected graph on N vertices needs at least N−1 edges to link all N components into one.
• A connected graph with exactly N−1 edges has no cycles (by counting argument: each extra edge creates exactly one cycle).
• Therefore: connected + N−1 edges ↔ connected + acyclic.

         1          <- root (depth 0)
        / \
       2   3        <- depth 1
      / \   \
     4   5   6      <- depth 2  (4, 5, 6 are leaves)

Tree Vocabulary

Rooting a Tree (Standard DFS Template)

Almost all tree problems require picking a root and computing parent/child relationships. The standard approach: read the tree as an undirected graph, then root with DFS:

int n;
cin >> n;
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);   // undirected tree edge
}

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

// Root at node 1 using iterative DFS (safe for N up to 10^5)
// Recursive DFS may stack-overflow for chains (N = 10^5 deep path)
function<void(int, int)> rootTree = [&](int u, int par) {
    parent[u] = par;
    for (int v : adj[u]) {
        if (v != par) {                // v != par avoids going back up
            children[u].push_back(v);
            depth[v] = depth[u] + 1;
            rootTree(v, u);
        }
    }
};
rootTree(1, 0);   // root = 1, sentinel parent = 0

After rootTree(1, 0) completes:

• parent[u] = parent of node u (0 if u is the root)
• children[u] = list of u's children in rooted tree
• depth[u] = depth of u from root

⚠️ Stack overflow warning for deep trees: Recursive DFS on a path graph of length 10^5 will overflow the default stack (typically 1–8 MB). For safety with large trees, use iterative DFS with an explicit stack, or increase stack size.

Iterative (stack-safe) version:

// Iterative rootTree: BFS-order, safe for any tree shape
vector<int> order;
queue<int> bfsQ;
vector<bool> visited(n + 1, false);
bfsQ.push(1);
visited[1] = true;
parent[1] = 0;
depth[1] = 0;

while (!bfsQ.empty()) {
    int u = bfsQ.front(); bfsQ.pop();
    order.push_back(u);
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            children[u].push_back(v);
            bfsQ.push(v);
        }
    }
}
// order[] = BFS traversal order (useful for bottom-up DP)

Preview: What Trees Enable

Trees have special structural properties that enable O(N) algorithms impossible on general graphs:

• Tree DP (Chapter 8.3): DP on subtrees
• LCA / Binary Lifting (Chapter 8.4): O(log N) ancestor queries
• Heavy-Light Decomposition: O(log² N) path queries (Gold/Platinum)
• Centroid Decomposition: O(N log N) distance problems (Platinum)

5.1.5 Weighted Graphs — Storing Edge Costs

So far, our edges have been "bare" — they just say "A connects to B." But many problems assign a cost to each edge (distance, travel time, capacity). Here's how to store that extra information.

// === Method 1: pair<int,int> — compact, common ===
vector<vector<pair<int,int>>> adj(n + 1);
// adj[u] stores {v, w} pairs

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

// Iterate with C++17 structured bindings:
for (auto& [v, w] : adj[u]) {
    cout << u << " -> " << v << " (cost " << w << ")\n";
}

// === Method 2: struct Edge — clearer for complex graphs ===
struct Edge {
    int to;       // destination vertex
    int weight;   // edge cost
};
vector<vector<Edge>> adj(n + 1);

// Add edge:
adj[u].push_back({v, w});

// Iterate:
for (const Edge& e : adj[u]) {
    relax(u, e.to, e.weight);
}

When to Use long long Weights

If edge weights can reach 10^9 and a path traverses multiple edges, the accumulated sum can overflow 32-bit int (max ~2.1×10^9):

Worst case: N = 10^5 nodes, all edge weights = 10^9
Longest possible path sum ≈ 10^5 × 10^9 = 10^14  → overflows int!

Safe template for Dijkstra / Bellman-Ford:

const long long INF = 2e18;   // safe sentinel for long long distances
vector<vector<pair<int, long long>>> adj(n + 1);
//                         ^^^^^^^^^^^ long long weight
vector<long long> dist(n + 1, INF);
dist[src] = 0;

Rule: If edge weights exceed 10^4 AND path length could exceed a few hundred edges, use long long. When in doubt, use long long — the performance difference is negligible.

5.1.6 Common Mistakes to Avoid

These are the bugs that trip up beginners most often. Memorize them — you'll save hours of debugging.

⚠️ Bug #1 — Missing reverse edge in undirected graph (most common!)

// WRONG: only adds one direction
adj[u].push_back(v);    // forgets adj[v].push_back(u) !

// CORRECT: undirected = both directions
adj[u].push_back(v);
adj[v].push_back(u);

Symptom: BFS/DFS visits only half the graph; some vertices appear unreachable.

⚠️ Bug #2 — Off-by-one in adjacency list size

// WRONG: size n, but vertex indices are 1..n → adj[n] out of bounds!
vector<vector<int>> adj(n);

// CORRECT: size n+1 for 1-indexed vertices
vector<vector<int>> adj(n + 1);

Symptom: Undefined behavior, random crashes, or incorrect results for the last vertex.

⚠️ Bug #3 — Local adjacency matrix crashes (stack overflow)

// WRONG: ~1 MB on stack → stack overflow
int main() {
    bool adj[1001][1001];   // local variable on stack!
}

// CORRECT: global array (BSS segment, auto zero-init)
bool adj[1001][1001];   // outside main()
int main() { ... }

⚠️ Bug #4 — Adjacency matrix used for large V (MLE)

// WRONG: V = 100,000 → 10 GB memory!
bool adj[100001][100001];

// CORRECT: use adjacency list for V > 1500
vector<vector<int>> adj(n + 1);

⚠️ Bug #5 — Grid bounds not checked before access

// WRONG: may access grid[-1][c] → undefined behavior!
if (grid[nr][nc] != '#') { ... }

// CORRECT: bounds check FIRST
if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] != '#') { ... }

⚠️ Bug #6 — Integer overflow in weighted graph distances

// WRONG: edge weight = 10^9, path has 10^5 edges → overflow
int dist[MAXN];

// CORRECT: use long long for distance arrays
long long dist[MAXN];
const long long INF = 2e18;

Chapter Summary

Here's everything from this chapter distilled into quick-reference tables.

Key Takeaways

Three Representations at a Glance

Graph: edges 1–2, 1–3, 2–4

Adjacency List:           Adjacency Matrix:         Edge List:
adj[1] = {2, 3}           adj:   1 2 3 4            edges:
adj[2] = {1, 4}             1  [ 0 1 1 0 ]            {1,2}
adj[3] = {1}                2  [ 1 0 0 1 ]            {1,3}
adj[4] = {2}                3  [ 1 0 0 0 ]            {2,4}
                            4  [ 0 1 0 0 ]
Space: O(V+E)             Space: O(V^2)             Space: O(E)
Neighbors: O(deg)         Edge check: O(1)          Sort: O(E log E)

Connections to Later Chapters

FAQ

Q: Should I use 0-indexed or 1-indexed vertices?

USACO input is almost always 1-indexed (vertices labeled 1 to N). Use vector<vector<int>> adj(n + 1) and leave slot 0 unused. This matches input directly and avoids off-by-one errors.

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

No. Grid neighbors are computed on-the-fly with dr[]/dc[] arrays — more memory-efficient and typically cleaner code.

Q: When should I use long long for edge weights?

When weights can reach 10^9 AND you might sum multiple edges (shortest path, total cost). The product 10^9 × path_length can easily exceed 2^31 − 1 ≈ 2.1×10^9. When in doubt, use long long.

Practice Problems

These problems test the concepts from this chapter. Start with the Easy ones to build confidence, then try the Medium ones to solidify your understanding.

Problem 5.1.1 — Degree Count 🟢 Easy

Problem: Read an undirected graph with N vertices and M edges. Print the degree of each vertex (number of edges incident to it).

Input:

N M
u₁ v₁
u₂ v₂
...

Sample Input 1:

4 4
1 2
2 3
3 4
4 1

Sample Output 1:

2 2 2 2

Sample Input 2:

5 3
1 2
1 3
1 4

Sample Output 2:

3 1 1 1 0

Constraints: 1 ≤ N ≤ 10^5, 0 ≤ M ≤ 2×10^5, 1 ≤ u, v ≤ N

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

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

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

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;   // undirected: both endpoints gain +1 degree
    }

    for (int u = 1; u <= n; u++) {
        cout << degree[u];
        if (u < n) cout << " ";
    }
    cout << "\n";

    return 0;
}
// Time: O(N + M),  Space: O(N)
// Verification: sum(degree) should equal 2*M (Handshaking Lemma)

Problem 5.1.2 — Is It a Tree? 🟢 Easy

Problem: Given a connected undirected graph with N vertices and M edges, determine if it is a tree.

Input: Standard edge list format.

5 4
1 2
1 3
3 4
3 5

4 4
1 2
2 3
3 4
4 1

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

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

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

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;   // read edges (not used in this simple check)
    }

    cout << (m == n - 1 ? "YES" : "NO") << "\n";
    return 0;
}
// Time: O(M),  Space: O(1)

N M S T
u₁ v₁
...

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

4 3 4 1
1 2
2 3
3 4

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

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

    int n, m, S, T;
    cin >> n >> m >> S >> T;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);   // directed: one direction only
    }

    vector<bool> visited(n + 1, false);
    queue<int> q;
    visited[S] = true;
    q.push(S);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    cout << (visited[T] ? "YES" : "NO") << "\n";
    return 0;
}
// Time: O(V + E),  Space: O(V + E)

N
p₂ p₃ ... pₙ

5
1 1 2 2

1

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

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

    int n;
    cin >> n;

    vector<bool> hasChild(n + 1, false);

    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        hasChild[parent] = true;   // parent has at least one child
    }

    int leaves = 0;
    for (int u = 1; u <= n; u++) {
        if (!hasChild[u]) leaves++;
    }

    cout << leaves << "\n";
    return 0;
}
// Time: O(N),  Space: O(N)

Input:  N=5,  parents: p[2]=1, p[3]=1, p[4]=2, p[5]=2
hasChild: [ _, true, true, false, false, false ]   (index 0 unused)
Leaves (hasChild=false): nodes 3, 4, 5  →  count = 3  ✓

3 3
...
.#.
...

2 2
..
..

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

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

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

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

    int edges = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '#') continue;
            // Check right neighbor
            if (c + 1 < m && grid[r][c+1] == '.') edges++;
            // Check bottom neighbor
            if (r + 1 < n && grid[r+1][c] == '.') edges++;
        }
    }

    cout << edges << "\n";
    return 0;
}
// Time: O(N*M),  Space: O(N*M)

. . .       Right edges: (0,0)-(0,1), (0,1)-(0,2), (2,0)-(2,1), (2,1)-(2,2) = 4
. # .       Down  edges: (0,0)-(1,0), (0,2)-(1,2), (1,0)-(2,0), (1,2)-(2,2) = 4
. . .       Total = 8  ✓

N M
u₁ v₁
...
Q
a₁ b₁
...

4 4
1 2
1 3
2 4
3 4

3
1 2
2 3
1 4

1
0
0

Constraints: 1 ≤ N ≤ 500, 0 ≤ M ≤ N*(N-1)/2, 1 ≤ Q ≤ 10^5

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

const int MAXV = 501;
bool adj[MAXV][MAXV];   // global: auto zero-initialized, no stack overflow

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

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

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

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (adj[a][b] ? 1 : 0) << "\n";   // O(1) per query!
    }

    return 0;
}
// Build: O(M),  Query: O(1) each,  Total: O(M + Q)
// Space: O(V^2) = O(500^2) = 250,000 bytes ≈ 250 KB  ✅
//
// With adjacency list: each query would be O(deg(a)) = up to O(N) per query
// = O(Q * N) = 10^5 * 500 = 5*10^7 — TLE risk. Matrix wins here!