Chapter 5.2: BFS & DFS

📝 Before You Continue: Make sure you understand graph representation (Chapter 5.1), queues and stacks (Chapter 3.6), and basic 2D array traversal (Chapter 2.3).

Graph traversal algorithms explore every node reachable from a starting point. They're the foundation of dozens of graph algorithms. DFS (Depth-First Search) dives deep before backtracking. BFS (Breadth-First Search) explores layer by layer. Knowing which to use and when is a skill you'll develop throughout your competitive programming career.

5.2.1 Depth-First Search (DFS)

DFS works like exploring a maze: you keep going forward until you hit a dead end, then backtrack and try another path.

Visual: DFS Traversal Order

DFS dives as deep as possible before backtracking. The numbered circles show the visit order, red dashed arrows show backtracking. The call stack on the right illustrates how recursion naturally implements the LIFO behaviour needed for DFS.

Recursive DFS

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

const int MAXN = 100001;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;           // mark current node as visited
    cout << u << " ";            // process u (print it, in this example)

    for (int v : adj[u]) {       // for each neighbor v
        if (!visited[v]) {       // if not yet visited
            dfs(v);              // recursively explore v
        }
    }
}

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].push_back(v);
        adj[v].push_back(u);
    }

    // DFS from node 1
    dfs(1);
    cout << "\n";

    return 0;
}

Important: Always mark nodes as visited before recursing, not after! This prevents infinite loops on cycles.

Iterative DFS (Using a Stack)

For very large graphs, recursive DFS can cause a stack overflow (too deep recursion). The iterative version uses an explicit stack:

void dfs_iterative(int start, int n) {
    vector<bool> visited(n + 1, false);
    stack<int> st;

    st.push(start);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (visited[u]) continue;  // may have been pushed multiple times
        visited[u] = true;
        cout << u << " ";

        for (int v : adj[u]) {
            if (!visited[v]) {
                st.push(v);
            }
        }
    }
}

5.2.2 Connected Components

A connected component is a maximal set of vertices where every vertex can reach every other vertex. Finding components is a very common USACO task.

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int comp[MAXN];   // comp[v] = component ID of vertex v

void dfs(int u, int id) {
    comp[u] = id;
    for (int v : adj[u]) {
        if (comp[v] == 0) {   // 0 means unvisited (use 0 as sentinel, 1-index components from 1)
            dfs(v, id);
        }
    }
}

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].push_back(v);
        adj[v].push_back(u);
    }

    int numComponents = 0;
    for (int u = 1; u <= n; u++) {
        if (comp[u] == 0) {
            numComponents++;
            dfs(u, numComponents);  // assign component ID
        }
    }

    cout << "Number of components: " << numComponents << "\n";

    // Print component sizes
    vector<int> size(numComponents + 1, 0);
    for (int u = 1; u <= n; u++) size[comp[u]]++;
    for (int i = 1; i <= numComponents; i++) {
        cout << "Component " << i << ": " << size[i] << " nodes\n";
    }

    return 0;
}

5.2.3 Breadth-First Search (BFS)

BFS explores all nodes at distance 1, then all at distance 2, then distance 3, and so on. This makes it perfect for finding shortest paths in unweighted graphs.

Visual: BFS Level-by-Level Traversal

BFS spreads outward like ripples in a pond. Each "level" of nodes is colored differently, showing that all nodes at distance d from the source are discovered before any node at distance d+1. The queue at the bottom shows the processing order.

BFS Template

// Solution: BFS Shortest Path — O(V + E)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];

// Returns array of shortest distances from source to all vertices
// dist[v] = -1 means unreachable
vector<int> bfs(int source, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[source] = 0;     // distance to source is 0
    q.push(source);       // seed the queue with the source

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] == -1) {          // not yet visited
                dist[v] = dist[u] + 1;   // ← KEY LINE: one hop further
                q.push(v);
            }
        }
    }

    return dist;
}

Why BFS Finds Shortest Paths

BFS processes nodes in order of their distance from the source. The first time BFS visits a node, it's via the shortest path. This is because BFS never visits a node at distance d+1 before visiting all nodes at distance d.

💡 Key Insight: Think of BFS as dropping a stone in water — ripples spread outward one layer at a time. All cells at distance 1 are processed before any cell at distance 2. This level-by-level processing guarantees the first visit to any node is via the shortest path.

BFS vs. DFS for shortest path:

• BFS: guaranteed shortest path in unweighted graphs ✓
• DFS: does NOT guarantee shortest path ✗

Complexity Analysis:

• Time: O(V + E) — each vertex and edge is processed at most once
• Space: O(V) — for the distance array and queue

Complete BFS Shortest Path Trace on a 4×4 Grid

Let's trace BFS starting from node 1 in this graph:

1 — 2 — 3
|       |
4 — 5   6
    |
    7 — 8

Edges: 1-2, 2-3, 1-4, 3-6, 4-5, 5-7, 7-8

BFS Trace:

Start: dist = [-1, 0, -1, -1, -1, -1, -1, -1, -1]  (1-indexed, source=1)
Queue: [1]

Process 1: neighbors 2, 4
  → dist[2] = 1, dist[4] = 1
  Queue: [2, 4]

Process 2: neighbors 1, 3
  → 1 already visited; dist[3] = 2
  Queue: [4, 3]

Process 4: neighbors 1, 5
  → 1 already visited; dist[5] = 2
  Queue: [3, 5]

Process 3: neighbors 2, 6
  → 2 already visited; dist[6] = 3
  Queue: [5, 6]

Process 5: neighbors 4, 7
  → 4 already visited; dist[7] = 3
  Queue: [6, 7]

Process 6: neighbor 3 → already visited
Process 7: neighbors 5, 8
  → 5 already visited; dist[8] = 4
  Queue: [8]

Process 8: neighbor 7 → already visited. Queue empty.

Final distances from node 1:
Node: 1  2  3  4  5  6  7  8
Dist: 0  1  2  1  2  3  3  4

5.2.4 Grid BFS — The Most Common USACO Pattern

Many USACO problems give you a grid with passable (.) and blocked (#) cells. BFS finds the shortest path from one cell to another.

Visual: Grid BFS Distance Flood Fill

Starting from the center cell (distance 0), BFS expands to all reachable cells, recording the minimum number of steps to reach each one. Cells colored more blue are farther away. This is exactly how USACO flood-fill and shortest-path problems work on grids.

USACO-Style Grid BFS Problem: Maze Shortest Path

Problem: Given a 5×5 maze with walls (#) and open cells (.), find the shortest path from top-left (0,0) to bottom-right (4,4). Print the length, or -1 if no path exists.

The Maze:

. . . # .
# # . # .
. . . . .
. # # # .
. . . . .

BFS Trace — Distance Array Filling:

Starting at (0,0), BFS expands level by level. Here's the distance each cell gets assigned:

Step 0 — Initialize:
dist[0][0] = 0, queue: [(0,0)]

Step 1 — Process (0,0):
  Neighbors: (0,1)='.', (1,0)='#'(wall)
  dist[0][1] = 1. Queue: [(0,1)]

Step 2 — Process (0,1):
  Neighbors: (0,0)=visited, (0,2)='.', (1,1)='#'
  dist[0][2] = 2. Queue: [(0,2)]

Step 3 — Process (0,2):
  Neighbors: (0,1)=visited, (0,3)='#', (1,2)='.'
  dist[1][2] = 3. Queue: [(1,2)]

Step 4 — Process (1,2):
  Neighbors: (0,2)=visited, (1,1)='#', (1,3)='#', (2,2)='.'
  dist[2][2] = 4. Queue: [(2,2)]

Step 5 — Process (2,2):
  Neighbors: (1,2)=visited, (2,1)='.', (2,3)='.', (3,2)='#'
  dist[2][1] = 5, dist[2][3] = 5. Queue: [(2,1),(2,3)]

...continuing BFS...

Final distance array (. = reachable, # = wall, X = unreachable):
    c=0  c=1  c=2  c=3  c=4
r=0:  0    1    2    #    X
r=1:  #    #    3    #    X
r=2:  8    5    4    5    6
r=3:  9    #    #    #    7
r=4: 10   11   12   11    8

Shortest path length = dist[4][4] = 8

Path reconstruction: Follow the path backward from (4,4), always moving to the cell with distance one less:

(4,4)=8 → (3,4)=7 → (2,4)=6 → (2,3)=5 → (2,2)=4 → (1,2)=3 → (0,2)=2 → (0,1)=1 → (0,0)=0
Path length: 8 steps ✓

ASCII Visualization of the path:

S → . → . # .
# # ↓ # .
. . ↓ → → →
. # # # ↓
. . . . E

Complete C++ Code:

// Solution: Grid BFS Shortest Path — O(R × C)
#include <bits/stdc++.h>
using namespace std;

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

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

    // Find start (S) and end (E), or use fixed corners
    int sr = 0, sc = 0, er = R-1, ec = C-1;

    // BFS distance array: -1 = unvisited
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    // Step 1: Seed BFS from source
    dist[sr][sc] = 0;
    q.push({sr, sc});

    // Step 2: Direction arrays (up, down, left, right)
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // Step 3: BFS expansion
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr >= 0 && nr < R           // in-bounds row
                && nc >= 0 && nc < C        // in-bounds col
                && grid[nr][nc] != '#'       // not a wall
                && dist[nr][nc] == -1) {     // ← KEY LINE: not yet visited

                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    // Step 4: Output result
    if (dist[er][ec] == -1) {
        cout << -1 << "\n";   // no path
    } else {
        cout << dist[er][ec] << "\n";
    }

    return 0;
}

Sample Input (the maze above):

5 5
...#.
##.#.
.....
.###.
.....

Sample Output:

8

⚠️ Common Mistake: Using DFS instead of BFS for shortest path in a maze. DFS might find A path, but not the SHORTEST path. Always use BFS for shortest distances in unweighted grids.

5.2.5 USACO Example: Flood Fill

USACO loves "flood fill" problems: find all connected cells of the same type, or count connected regions.

Problem: Count the number of distinct connected regions of '.' cells in a grid. (Like counting islands.)

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

int R, C;
vector<string> grid;
vector<vector<bool>> visited;

void floodFill(int r, int c) {
    if (r < 0 || r >= R || c < 0 || c >= C) return;  // out of bounds
    if (visited[r][c]) return;                          // already visited
    if (grid[r][c] == '#') return;                      // wall

    visited[r][c] = true;

    floodFill(r - 1, c);  // up
    floodFill(r + 1, c);  // down
    floodFill(r, c - 1);  // left
    floodFill(r, c + 1);  // right
}

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

    cin >> R >> C;
    grid.resize(R);
    visited.assign(R, vector<bool>(C, false));

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

    int regions = 0;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (!visited[r][c] && grid[r][c] == '.') {
                regions++;
                floodFill(r, c);
            }
        }
    }

    cout << regions << "\n";
    return 0;
}

5.2.6 Multi-Source BFS

Sometimes you start BFS from multiple source nodes simultaneously. For example: "Find the minimum distance from each cell to the nearest fire."

// Multi-source BFS: start from all fire cells at once
queue<pair<int,int>> q;
vector<vector<int>> dist(R, vector<int>(C, -1));

// Push ALL sources first
for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
        if (grid[r][c] == 'F') {  // fire cell
            dist[r][c] = 0;
            q.push({r, c});
        }
    }
}

// Run BFS from all sources simultaneously
while (!q.empty()) {
    auto [r, c] = q.front();
    q.pop();
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (/*valid and unvisited*/ nr >= 0 && nr < R && nc >= 0 && nc < C && dist[nr][nc] == -1) {
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
}

5.2.7 DFS vs. BFS — When to Use Each

💡 Key Insight: Use BFS whenever you need "the minimum number of steps." Use DFS whenever you just need to visit all nodes or check properties of paths.

⚠️ Common Mistakes in Chapter 5.2

1. Using DFS for shortest path: DFS explores one path deeply and doesn't guarantee minimum steps. Always use BFS for unweighted shortest paths.
2. Forgetting bounds check: nr >= 0 && nr < R && nc >= 0 && nc < C — missing any one of these four conditions causes out-of-bounds crashes.
3. Not marking visited before pushing to queue: If you mark visited when popping instead of pushing, the same node can be pushed multiple times, causing O(V²) time instead of O(V+E).
4. Stack overflow in recursive DFS: For grids with N×M = 10^6, recursive DFS can exceed the default stack size. Use iterative DFS or increase stack size.
5. Using wrong starting point: In grid problems, make sure you're BFSing from the correct cell (0-indexed vs 1-indexed confusion).

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Both BFS and DFS have time complexity O(V+E). Why can BFS find shortest paths but DFS cannot?

A: The key is visit order. BFS uses a queue to guarantee "process all nodes at distance d before distance d+1," so the first time a node is reached is always via the shortest path. DFS uses a stack (or recursion) and may take a long path to a node, missing shorter ones.

Q2: When does recursive DFS cause stack overflow? How to fix it?

A: Default stack size is ~1-8 MB. Each recursion level uses ~100-200 bytes. When graph depth exceeds ~10^4-10^5, overflow may occur. Solutions: ① Switch to iterative DFS (explicit stack); ② Add -Wl,-z,stacksize=67108864 at compile time to increase stack size.

Q3: In Grid BFS, why use dist == -1 for unvisited instead of a visited array?

A: Using dist[r][c] == -1 kills two birds with one stone: it records both "visited or not" and "distance to reach." One fewer array, cleaner code.

Q4: When to use DFS topological sort vs. Kahn's BFS topological sort?

A: DFS topological sort has shorter code (just reverse postorder), but Kahn's is more intuitive and can detect cycles (if final sorted length < N, there is a cycle). Both are common in contests; choose whichever you're more comfortable with.

🔗 Connections to Later Chapters

• Chapter 5.3 (Trees & DSU): Tree Traversal (pre/postorder) is essentially DFS
• Chapters 5.3 & 6.1–6.3 (DP): "DP on DAG" requires topological sort first, then compute DP in topological order
• Chapter 4.1 (Greedy): Some graph greedy problems need BFS to compute distances as input
• BFS shortest path is a simplified version of Dijkstra (Gold level)—Dijkstra handles weighted graphs, BFS handles unweighted
• Multi-source BFS is extremely common in USACO Silver and is a must-master core technique

Practice Problems

Problem 5.2.1 — Island Count 🟢 Easy Read an N×M grid of '.' (water) and '#' (land). Count the number of islands (connected groups of '#').

Problem 5.2.2 — Maze Shortest Path 🟢 Easy Read an N×M maze with 'S' (start), 'E' (end), '.' (passable), '#' (wall). Find the minimum steps from S to E, or -1 if impossible.

Problem 5.2.3 — Bipartite Check 🟡 Medium A graph is bipartite if you can color each node black or white such that every edge connects a black node to a white node. Given a graph, determine if it's bipartite.

Solution sketch: BFS and 2-color. When you visit a node, color it the opposite of its parent. If you ever find an edge between two same-colored nodes, it's not bipartite.

Problem 5.2.4 — Multi-Source BFS: Nearest Fire 🟡 Medium Given a grid with fire cells 'F', empty cells '.', and walls '#', find the minimum distance from each empty cell to the nearest fire cell.

Solution sketch: Initialize the BFS queue with ALL fire cells at distance 0. Run BFS normally. Each empty cell gets the distance to its nearest fire.

Problem 5.2.5 — USACO 2016 February Bronze: Milk Pails 🔴 Hard Starting from a state (0, 0) of two buckets with capacities A and B, operations: fill A (→ capacity A), fill B, pour A into B, pour B into A, empty A, empty B. Find minimum operations to get exactly X gallons in either bucket.

Solution sketch: BFS on states (a, b) where a ∈ [0,A] and b ∈ [0,B]. Each state is a node, each operation is an edge. BFS from (0,0) finds minimum operations.

🏆 Challenge Problem: USACO 2015 December Bronze: Switching on the Lights You have an N×N grid of light switches. Each switch is connected to some lights. Turn on all lights by flipping switches. Model as a BFS/DFS graph reachability problem where turning on a light may reveal new switches.

This requires multi-source BFS + careful state management.

5.2.8 Multi-Source BFS — In Depth

Multi-source BFS starts from multiple source nodes simultaneously. The key: push all sources into the queue at distance 0 before starting BFS.

Why does this work? BFS processes nodes level by level. If multiple nodes start at "level 0," BFS naturally propagates from all of them in parallel — exactly as if you had a virtual super-source connected to all real sources at cost 0.

Level 0:    [S₁][S₂][S₃]    ← all fire sources / all starting nodes
Level 1:   neighbors of S₁, S₂, S₃
Level 2:   their neighbors not yet visited
...

Complete Example: Spreading Fire

Problem: Given an N×M grid with fire cells ('F'), water cells ('.'), and walls ('#'), compute the minimum distance from each '.' cell to the nearest fire cell.

// Solution: Multi-Source BFS — O(N×M)
#include <bits/stdc++.h>
using namespace std;

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

    int R, C;
    cin >> R >> C;
    vector<string> grid(R);
    for (auto& row : grid) cin >> row;

    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;

    // ← KEY: Push ALL fire sources at distance 0 before starting BFS
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (grid[r][c] == 'F') {
                dist[r][c] = 0;
                q.push({r, c});
            }
        }
    }

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

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    // Print distance grid
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (dist[r][c] == -1) cout << " # ";
            else cout << " " << dist[r][c] << " ";
        }
        cout << "\n";
    }

    return 0;
}

BFS Level Visualization:

Level 0:    [F₁][F₂]          ← all fire sources enter queue together
Level 1:   [ 1 ][ 1 ][ 1 ]    ← cells adjacent to any fire source
Level 2:  [ 2 ][ 2 ][ 2 ][ 2 ]
Level 3: [ 3 ][ 3 ][ 3 ][ 3 ][ 3 ]

Multi-Source BFS 层级扩散示意：

flowchart TD
    subgraph L0["Level 0 — 初始火源"]
        F1(["F₁\ndist=0"]) 
        F2(["F₂\ndist=0"])
    end
    subgraph L1["Level 1 — 第一层扩散"]
        N1(["dist=1"])
        N2(["dist=1"])
        N3(["dist=1"])
    end
    subgraph L2["Level 2 — 第二层扩散"]
        N4(["dist=2"])
        N5(["dist=2"])
    end
    F1 --> N1
    F1 --> N2
    F2 --> N2
    F2 --> N3
    N1 --> N4
    N3 --> N5
    style F1 fill:#fca5a5,stroke:#dc2626
    style F2 fill:#fca5a5,stroke:#dc2626
    style L0 fill:#fff1f2
    style L1 fill:#fef9ec
    style L2 fill:#f0fdf4

💡 关键原理： 所有火源同时入队（dist=0），BFS 自然地并行向外扩散。每个空白格子得到的是到最近火源的最短距离——这是 BFS 层序性质的直接推论。

Each cell gets the minimum distance to any fire source — guaranteed by BFS's level-order property.

USACO Application: "Icy Perimeter" Style

Multi-source BFS is useful when you need:

• "Distance from each cell to nearest [thing]"
• "Spreading from multiple starting points" (fire, infection, flood)
• "Simultaneous evacuation from multiple exits"

5.2.9 Cycle Detection with DFS — White/Gray/Black Coloring

For directed graphs, cycle detection uses 3-color DFS:

• White (0): Not yet visited
• Gray (1): Currently in DFS call stack (being processed)
• Black (2): Fully processed (all descendants explored)

A back edge (edge to a gray node) indicates a cycle.

// Solution: Cycle Detection in Directed Graph — O(V+E)
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100001];
vector<int> color;   // 0=white, 1=gray, 2=black
bool hasCycle = false;

void dfs(int u) {
    color[u] = 1;  // mark as "in progress" (gray)

    for (int v : adj[u]) {
        if (color[v] == 0) {
            dfs(v);              // unvisited: recurse
        } else if (color[v] == 1) {
            hasCycle = true;     // ← back edge: v is an ancestor of u → cycle!
        }
        // color[v] == 2: already fully processed, safe to skip
    }

    color[u] = 2;  // mark as "done" (black)
}

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

    int m;
    cin >> n >> m;
    color.assign(n + 1, 0);

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

    for (int u = 1; u <= n; u++) {
        if (color[u] == 0) dfs(u);
    }

    cout << (hasCycle ? "HAS CYCLE" : "NO CYCLE") << "\n";
    return 0;
}

⚠️ Undirected graph cycle detection: For undirected graphs, use a simpler method: during DFS, if you visit a node that's already visited AND it's not the parent of the current node, there's a cycle. Alternatively, use DSU: if an edge connects two already-connected nodes, it creates a cycle.

5.2.10 Topological Sort with DFS

Topological sort orders the nodes of a directed acyclic graph (DAG) such that for every edge u → v, u comes before v.

DFS approach: When a node finishes (all descendants processed), add it to the front of the result list. This gives reverse topological order.

Finish order (post-order):  E, D, C, B, A
Topological order (reverse): A, B, C, D, E

// Solution: Topological Sort via DFS — O(V+E)
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100001];
vector<bool> visited;
vector<int> topoOrder;

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
    topoOrder.push_back(u);  // ← add AFTER all children processed (post-order)
}

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

    int n, m;
    cin >> n >> m;
    visited.assign(n + 1, false);

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

    for (int u = 1; u <= n; u++) {
        if (!visited[u]) dfs(u);
    }

    // Reverse post-order = topological order
    reverse(topoOrder.begin(), topoOrder.end());

    for (int u : topoOrder) cout << u << " ";
    cout << "\n";

    return 0;
}

Alternative: Kahn's Algorithm (BFS-based Topological Sort)

// Kahn's Algorithm: Process nodes with in-degree 0 first — O(V+E)
vector<int> inDeg(n + 1, 0);
for (int u = 1; u <= n; u++)
    for (int v : adj[u])
        inDeg[v]++;

queue<int> q;
for (int u = 1; u <= n; u++)
    if (inDeg[u] == 0) q.push(u);  // start with nodes having no prerequisites

vector<int> order;
while (!q.empty()) {
    int u = q.front(); q.pop();
    order.push_back(u);
    for (int v : adj[u]) {
        inDeg[v]--;
        if (inDeg[v] == 0) q.push(v);
    }
}

// If order.size() != n, there's a cycle (not a DAG)
if ((int)order.size() != n) cout << "CYCLE DETECTED\n";
else for (int u : order) cout << u << " ";

Kahn 算法入度变化过程：

flowchart LR
    subgraph init["初始入度"]
        direction TB
        A0(["A\nin=0"]) 
        B0(["B\nin=1"])
        C0(["C\nin=2"])
        D0(["D\nin=1"])
    end
    subgraph step1["处理 A（in=0）"]
        direction TB
        A1(["A\n已处理"]) 
        B1(["B\nin=0↓"])
        C1(["C\nin=2"])
        D1(["D\nin=1"])
    end
    subgraph step2["处理 B（in=0）"]
        direction TB
        A2(["A\n已处理"]) 
        B2(["B\n已处理"])
        C2(["C\nin=1↓"])
        D2(["D\nin=0↓"])
    end
    subgraph step3["处理 D→C（in=0）"]
        direction TB
        A3(["A"]) 
        B3(["B"])
        C3(["C\nin=0↓"])
        D3(["D\n已处理"])
    end
    init -->|"将 A 入队"| step1
    step1 -->|"将 B 入队"| step2
    step2 -->|"将 D,C 入队"| step3
    style A0 fill:#dcfce7,stroke:#16a34a
    style B1 fill:#dcfce7,stroke:#16a34a
    style D2 fill:#dcfce7,stroke:#16a34a
    style C3 fill:#dcfce7,stroke:#16a34a

💡 循环检测： 若最终 order.size() < n，说明有节点的入度始终不为 0（它们在环中）。这是 Kahn 算法相比 DFS 拓扑排序的一大优势。

💡 Key Application: Topological sort is essential for DP on DAGs. If the dependency graph is a DAG, process nodes in topological order — each node's DP state depends only on previously-processed nodes.

Example DAG and BFS levels visualization:

Visual: Grid BFS Distances from Source

The diagram shows a 5×5 grid BFS where each cell displays its minimum distance from the source (0,0). Walls are shown in dark gray. Note how the BFS "flood fills" outward in concentric rings, never revisiting a cell — guaranteeing minimum distances.