Chapter 11: Trees & Graph Theory Basics

11.1 Representing a Graph

A graph consists of vertices and edges. Suppose there are N vertices and M edges.

11.1.1 Adjacency Matrix

The most intuitive method uses a 2D array g[N][N].

• g[u][v] = 1 or w: there is an edge (weight w) between u and v.
• g[u][v] = 0 or INF: no edge exists.

int g[1005][1005];
memset(g, 0x3f, sizeof(g));
 
// Add edge u -> v with weight w
g[u][v] = w;
// For undirected graphs, also add g[v][u]
g[v][u] = w;

• Pros: O(1) query for whether edge exists.
• Cons: extremely memory hungry. With N = 10^5, int g[100000][100000] would blow memory.
• Use when: dense graphs with N ≤ 1000.

11.1.2 Adjacency List (CP Standard)

Store only existing edges using vector. vector<int> adj[N]: adj[u] stores all neighbors reachable from u.

vector<int> adj[100005];
 
int main() {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    // For undirected graphs:
    // adj[v].push_back(u);
}

• Iteration pattern:

for (int v : adj[u]) {
    // v is a neighbor of u
}

• Pros: memory scales with the number of edges M, not N^2.
• Use for: most grapht problems with N, M ≤ 10^5.

11.2 Trees: A Special Graph

A tree is a connected graph with no cycles. It has N nodes and exactly N−1 edges.

11.2.1 Concepts

• Root: the top node (usually node 1).
• Leaf: a node without children (degree = 1).
• Depth: root depth = 1 (or 0), and each level increases by 1.
• Parent & Child: along any edge, the node closer to the root is the parent.

11.2.2 Properties

Because trees contain no cycles, there is only one path between any two nodes A and B.

• LCA (Least Common Ancestor): The first common ancestor encountered when climbing u and v upward. Like a family tree where you and your cousin share a grandparent.
• Diameter: The longest path between any two nodes.

11.3 Topological Sort

Not sorting numbers, but tasks.

Scenario: You have four courses:

• A: C++ Basics (no prerequisites)
• B: Data Structures (requires A)
• C: Advanced Algorithms (requires B)
• D: Graduation Project (requires C)

A valid order is A → B → C → D. That is a topological order.

Topological sort applies only to DAGs (Directed Acyclic Graphs). If a cycle exists (A depends on B, B depends on A), no order exists.

11.3.1 Kahn’s Algorithm (Using Indegrees)

1. Indegree: the number of edges pointing into a node.
   • A node with indegree 0 has no prerequisites and can be processed.
2. Algorithm:
   • Push all nodes with indegree 0 into a queue.
   • While the queue is not empty:
     • Pop u, add it to the result.
     • For each neighbor v of u, decrement in_degree[v].
     • If in_degree[v] == 0, push v into the queue.
   • If the result contains all n nodes, a topological order exists. Otherwise, there is a cycle.

Template

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
vector<int> adj[10005];
int in_degree[10005];
vector<int> result;
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in_degree[v]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u);
        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) q.push(v);
        }
    }
 
    if (result.size() == n) {
        // output result
    } else {
        cout << "Cycle detected; no topological order" << endl;
    }
    return 0;
}

🧠 Summary & Practice

Graph theory starts with building the graph. If you can store edges in vectors, you’ve cleared half the battle. Topological sorting handles dependency problems.

Exercises:

1. P5318 Bibliography Search (Luogu): practice building graphs and traversal.
2. P4017 Maximum Food Chain: DAG DP that relies on topological ordering.
3. B3644 Topological Sort / Family Tree: apply the template directly.

This chapter completes your introduction to graph basics. More advanced topics await in the following sections.