Skip to content

DFS on Graphs

Trees Lied to You About DFS

Visited array progression as DFS explores each node

DFS tree showing tree edges, back edges, and cross edges

DFS traversal order with stack states at each step

Tree DFS never worries about visiting the same node twice. Parent points to child, child never points back. You recurse down, you return up, done.

Graphs break this. A graph can have cycles, and a cycle means your DFS will loop forever unless you track what you've already seen. The visited array is the single most important addition when moving from tree DFS to graph DFS.

Why Trees Don't Need Visited

In a rooted tree, every edge goes from parent to child. When you call dfs(child) from dfs(parent), the child has no way to reach the parent again through its own children. The structure prevents revisits.

Tree: edges only go down          Graph: edges can go anywhere

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

In the graph on the right, starting DFS at node 1: visit 1, visit 2, visit 3, visit 4... and 4 connects back to 1. Without a visited check, you'd loop through 1-2-3-4-1-2-3-4 forever.

⚠ Gotcha. Every graph DFS must check visited before recursing. Forgetting this causes infinite loops or stack overflows. No exceptions.

The Graph DFS Template

Here's the template. Compare it to tree DFS -- the only additions are the visited array and the if (!visited[v]) guard.

bool visited[200005];
vector<int> adj[200005];

void dfs(int u) {
    visited[u] = true;       // mark BEFORE recursing
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

Three differences from tree DFS:

  1. visited array replaces the structural guarantee of parent-child edges.
  2. Iterate over adj[u] instead of left/right -- graphs have arbitrary neighbors.
  3. Mark visited at entry, not at the call site. This prevents double-processing.

💡 Key insight. Tree DFS has an implicit visited guarantee: the tree structure itself prevents revisits. Graph DFS must make that guarantee explicit.

DFS Trace on a Graph

Consider this undirected graph with 6 nodes and 7 edges:

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

Adjacency list (sorted neighbors):

  • 1: [2, 4]
  • 2: [1, 3]
  • 3: [2, 5, 6]
  • 4: [1, 5]
  • 5: [3, 4]
  • 6: [3]

DFS starting from node 1:

Step Current Visited Set Action Stack State
1 1 {1} Visit 1, try neighbor 2 [1]
2 2 {1,2} Visit 2, try neighbor 1 (visited), try 3 [1,2]
3 3 {1,2,3} Visit 3, try 2 (visited), try 5 [1,2,3]
4 5 {1,2,3,5} Visit 5, try 3 (visited), try 4 [1,2,3,5]
5 4 {1,2,3,4,5} Visit 4, try 1 (visited), try 5 (visited) [1,2,3,5,4]
6 -- {1,2,3,4,5} Backtrack from 4, backtrack from 5, try 6 [1,2,3]
7 6 {1,2,3,4,5,6} Visit 6, try 3 (visited), backtrack [1,2,3,6]

DFS order: 1, 2, 3, 5, 4, 6.

Notice how "try 1 (visited)" at step 2 and "try 3 (visited)" at step 4 are the moments where visited prevents infinite loops. Without it, step 2 would recurse back into node 1 and we'd never finish.

Connected Components

An undirected graph might not be connected. There could be isolated clusters with no edges between them. Each cluster is a connected component.

To count components: run DFS from each unvisited node. Each DFS call explores one entire component.

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

Component 1:  1 --- 2       Component 2:  5 --- 6
              |                            |
              3 --- 4                      7

First DFS from node 1 visits {1, 2, 3, 4}. Nodes 5, 6, 7 are still unvisited. Second DFS from node 5 visits {5, 6, 7}. Two components total.

Component Counting Trace

Outer Loop i visited[i]? Action Components
1 No DFS(1) visits 1
2 Yes Skip 1
3 Yes Skip 1
4 Yes Skip 1
5 No DFS(5) visits 2
6 Yes Skip 2
7 Yes Skip 2

Total components: 2

💡 Key insight. "Building roads" between disconnected components requires exactly components - 1 new edges. That's CSES Building Roads in one line of logic.

Cycle Detection in Undirected Graphs

If during DFS you visit a neighbor that is already visited and it's not your parent, you've found a cycle.

Why the parent check? In an undirected graph, if node 2 was reached from node 1, then node 1 appears in adj[2]. Seeing node 1 from node 2 doesn't mean there's a cycle -- it's just the edge you arrived on. But if you see a visited node that isn't your parent, you've found a back edge, and back edges mean cycles.

int par[200005];
int cycleStart = -1, cycleEnd = -1;

bool dfs(int u, int p) {
    visited[u] = true;
    par[u] = p;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (dfs(v, u)) return true;
        } else if (v != p) {
            cycleStart = v;
            cycleEnd = u;
            return true;
        }
    }
    return false;
}

Cycle Detection Trace

Consider this graph:

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

DFS from node 1 (parent = 0, meaning none):

Step u parent Neighbor v visited[v]? v == parent? Action
1 1 0 2 No -- Recurse into 2
2 2 1 1 Yes Yes Skip (parent edge)
3 2 1 3 No -- Recurse into 3
4 3 2 2 Yes Yes Skip (parent edge)
5 3 2 4 No -- Recurse into 4
6 4 3 1 Yes No Cycle found! cycleStart=1, cycleEnd=4

At step 6, node 4 sees neighbor 1, which is visited but is NOT its parent (parent is 3). That's a cycle.

⚠ Gotcha. The parent check only works for simple graphs (no multi-edges). If there are two edges between nodes u and v, seeing v from u after arriving from v IS a cycle, but the parent check would skip it. For multi-edge graphs, track the edge index instead of the parent node.

Reconstructing the Cycle Path

Finding a cycle exists is easy. Printing the actual cycle -- as required by CSES Round Trip -- takes one more step.

When you detect the cycle (cycleStart = v, cycleEnd = u), the path from cycleStart to cycleEnd lives in the parent[] chain. Walk backwards from cycleEnd to cycleStart:

vector<int> cycle;
cycle.push_back(cycleStart);
for (int v = cycleEnd; v != cycleStart; v = par[v]) {
    cycle.push_back(v);
}
cycle.push_back(cycleStart);
reverse(cycle.begin(), cycle.end());

For our example (cycleStart = 1, cycleEnd = 4):

Walk Step Current Node parent[current] Path So Far
Start 4 3 [1, 4]
1 3 2 [1, 4, 3]
2 2 1 [1, 4, 3, 2]
Stop 1 == cycleStart -- [1, 4, 3, 2, 1]

After reversing: 1 -> 2 -> 3 -> 4 -> 1. That's the cycle.

Pre-Order vs Post-Order in Graph DFS

Just like tree DFS, graph DFS has two useful moments per node: entering (pre-order) and leaving (post-order).

int timer = 0;
int tin[200005], tout[200005];

void dfs(int u, int p) {
    visited[u] = true;
    tin[u] = timer++;    // pre-order: entering node u
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, u);
        }
    }
    tout[u] = timer++;   // post-order: leaving node u
}
  • Pre-order (tin): when you first discover the node. Useful for DFS ordering, timestamps.
  • Post-order (tout): when you've finished exploring all reachable nodes from it. Essential for topological sort, SCC detection, and bridge-finding.

On the graph 1-2-3-5-4-6 from our earlier trace:

Node tin (enter) tout (leave)
1 0 11
2 1 10
3 2 9
5 3 6
4 4 5
6 7 8

💡 Key insight. If tin[u] < tin[v] and tout[u] > tout[v], then v was discovered and finished during u's DFS call. This means v is a descendant of u in the DFS tree. This ancestor/descendant test comes up repeatedly in later chapters.

The DFS Tree

When DFS explores a graph, it implicitly builds a DFS tree. The edges used to discover new nodes (the ones where !visited[v] was true) form a spanning tree of each component.

The remaining edges -- where visited[v] was already true -- are called back edges (in undirected graphs). These are exactly the edges that create cycles.

Graph:              DFS Tree:           Back edges:
1 --- 2             1                   4 → 1 (creates cycle 1-2-3-4)
|     |             |
4 --- 3             2
                    |
                    3
                    |
                    4

Every undirected graph has exactly one DFS tree per component (for a given starting node and neighbor ordering). The number of back edges equals the number of independent cycles.

Try It

The starter code has a DFS that detects whether a cycle exists but doesn't print it yet. Add cycle path reconstruction.

Test case 1 -- graph with a cycle: 

Input:
4 4
1 2
2 3
3 4
4 1

Output:
1 2 3 4 1

Test case 2 -- graph without a cycle (a tree): 

Input:
4 3
1 2
2 3
3 4

Output:
No cycle found

Challenge: What happens if the graph has multiple connected components, some with cycles and some without? Does the code handle this correctly? (Yes -- the outer loop tries each unvisited node, and the first component with a cycle will be found.)

Challenge 2: Modify the code to count the number of connected components AND detect if any component has a cycle. Print both: the component count and whether a cycle exists.

Problems

Problem Link Difficulty
CSES Building Roads cses.fi/problemset/task/1666 Easy
CSES Round Trip cses.fi/problemset/task/1669 Medium
LC 323 — Number of Connected Components leetcode.com/problems/number-of-connected-components-in-an-undirected-graph Medium
LC 261 — Graph Valid Tree leetcode.com/problems/graph-valid-tree Medium