Depth First Search

DFS explores as far as possible along each branch before backtracking. $O (V + E)$ — every vertex and edge is touched once.

By itself DFS answers almost nothing. Its value is as the skeleton of a dozen other algorithms: connected components, cycle detection, bipartiteness, topological sort, bridges and articulation points, SCCs, Euler tours, augmenting paths in flows, and maze generation.

Recursive

int n;
vector<vector<int>> adj;
vector<int> visited;
 
void dfs(int u) {
    visited[u] = 1;
    for (int v : adj[u])
        if (!visited[v]) dfs(v);
}

Iterative

Use this when the graph is deep — the default stack blows up around $1 0^{5}$ frames on most judges.

void dfsIterative(int start) {
    vector<int> visited(n, 0);
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for (int v : adj[u])
            if (!visited[v]) st.push(v);
    }
}

Stack overflow
Recursive DFS on a path graph of $1 0^{6}$ vertices will crash. Options: rewrite iteratively, or (on Codeforces) raise the stack with a thread:
int main() { thread t(solve, 0, 0, 256 << 20); t.join(); }
The iterative rewrite is the portable answer.

Edge classification

DFS partitions the edges of a directed graph into four kinds. Recognising them is what makes the derived algorithms work.

Edge type	Condition (using `tin`/`tout` timestamps)	Meaning
Tree	`v` unvisited when explored from `u`	part of the DFS forest
Back	`v` is an ancestor: `tin[v] < tin[u] < tout[u] < tout[v]`	a cycle exists
Forward	`v` is a descendant already finished	a shortcut down the tree
Cross	neither ancestor nor descendant	between different subtrees

In an undirected graph there are only tree and back edges — which is why “back edge ⟺ cycle” is a complete test there.

The timestamp pattern

Almost every advanced DFS algorithm is this skeleton plus a little bookkeeping:

int timer = 0;
vector<int> tin, tout;
 
void dfs(int u, int p) {
    tin[u] = timer++;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (!tin[v]) dfs(v, u);       // tree edge
        else { /* back / cross edge — update low-link, detect cycle, ... */ }
    }
    tout[u] = timer++;
}

With tin/tout you get, for free:

“is $u$ an ancestor of $v$ ?” in $O (1)$ : tin[u] <= tin[v] && tout[v] <= tout[u]
subtree as a contiguous range — the basis of Euler tour subtree queries
low[u] (the earliest reachable ancestor) — the basis of Tarjan’s bridges, articulation points, and SCCs

Common uses at a glance

Task	Extra state
Connected components	a component id per vertex
Cycle detection (directed)	a colour array: white / grey / black
Cycle detection (undirected)	parent, plus “visited neighbour that is not the parent”
Topological sort	push on exit, then reverse
Bridges / articulation points	`tin` and `low`
SCC	`tin`, `low`, an explicit stack
Subtree sizes	accumulate on return
Tree DP	accumulate on return

See also: Breadth First Search · Cycle Detection · Euler Tour

whoashish's cp notes

Directory