ii. BFS, DFS and Grids

BFS visits vertices in order of distance (in edges) and gives unweighted shortest paths; DFS gives a tree with timestamps whose structure (back edges, subtree intervals, lowlinks) drives cycles, topological order, bridges, SCCs and Euler tours. Both are $O(n+m)$.

BFS

vector<int> bfs(const vector<vector<int>>& g, const vector<int>& sources) {   // multi-source
    vector<int> d(sz(g), -1); queue<int> q;
    for (int s : sources) if (d[s] < 0) d[s] = 0, q.push(s);
    while (sz(q)) { int u = q.front(); q.pop(); for (int v : g[u]) if (d[v] < 0) d[v] = d[u] + 1, q.push(v); }
    return d;
}

Mark when pushing, not when popping, so each vertex enters the queue once. Keep par[v] = u to recover paths.

Proof: BFS distances are shortest

Invariant: the queue holds vertices with distances $d,\dots ,d,d+1,\dots ,d+1$ (nondecreasing, spread $\le 1$), and every vertex at true distance $<d$ has already been popped. When $u$ (distance $d$) is popped, its unvisited neighbours get $d+1$, keeping the invariant. By induction on the true distance $k$: a vertex $v$ at distance $k$ has a neighbour $w$ on a shortest path at distance $k-1$, which is popped with label $k-1$; at that moment $v$ is labelled $k$ unless it was already labelled, and any earlier label is $\le k$ (labels are nondecreasing in pop order) and $\ge k$ (labels are lengths of real paths). Multi-source BFS is the same on a graph with a super-source joined to all sources.

Variants:

• Grids: direction arrays, cell id $r\cdot m+c$; mark walls/visited in place.
• Multi-source: “distance to the nearest X”; fire spreading. For “escape before the monsters”: BFS from all monsters first, then BFS for the player using only cells reached strictly earlier than the monsters (CSES Monsters).
• State BFS: vertices $(v,\text{mask})$, $(r,c,\text{direction})$, $(r,c,\text{steps mod }k)$.
• Bidirectional BFS: expand the smaller frontier; $O(b^{d/2})$ instead of $O(b^d)$ on puzzle state spaces. Stop when a full layer has been expanded and the frontiers meet; take the minimum over meeting edges.
• Weights 0/1 or small integers: 0-1 BFS, Dial’s buckets (Shortest Paths).
• Lexicographically smallest shortest path: BFS from the target for distances, then walk from the source choosing the smallest label among neighbours with distance one less, processing whole layers at once (keep the set of current best vertices).

BFS on the complement graph

The complement of a sparse graph is dense, but BFS on it costs $O(n+m)$: keep the unvisited vertices in a list; when expanding $u$, every unvisited vertex not adjacent to $u$ (in the sparse graph) is visited and removed for good, and every vertex that stays is paid for by an edge of the sparse graph.

vector<int> complementBFS(const vector<vector<int>>& g, int s) {   // g = edges NOT present
    int n = sz(g); vector<int> d(n, -1), mark(n, -1), rest; queue<int> q;
    for (int v = 0; v < n; v++) if (v != s) rest.push_back(v);
    d[s] = 0; q.push(s);
    while (sz(q)) {
        int u = q.front(); q.pop();
        for (int v : g[u]) mark[v] = u;
        vector<int> keep;
        for (int v : rest) if (mark[v] == u) keep.push_back(v); else d[v] = d[u] + 1, q.push(v);
        rest.swap(keep);
    }
    return d;
}

Components of the complement (CF 920E) and MST of a complete graph with 0/1 weights (CF 1242B) use the same loop.

Proof: $O(n+m)$

When $u$ is expanded, each vertex scanned in rest is either removed (at most $n$ times overall) or kept, and it is kept only if $(u,v)$ is an edge of the sparse graph. Each vertex is expanded once, so each sparse edge causes at most two “keep” events. Total $O(n+m)$.

Knight distance on an unbounded board

ll knightDist(ll x, ll y) {                                // offset (x, y), unbounded board
    x = llabs(x), y = llabs(y); if (x < y) swap(x, y);
    if (x == 1 && y == 0) return 3;
    if (x == 2 && y == 2) return 4;
    ll k = max((x + 1) / 2, (x + y + 2) / 3);
    if ((k - x - y) % 2) k++;
    return k;
}

On a bounded board, corners change small distances (corner to its diagonal neighbour needs 4), so BFS there.

Proof sketch: the knight formula

Lower bounds: a move changes $x$ by at most 2 and $x+y$ by at most 3, so $k\ge \lceil x/2\rceil$ and $k\ge \lceil (x+y)/3\rceil$; each move changes $x+y$ by $\pm 1$ or $\pm 3$ (an odd number), so $k\equiv x+y(\mathrm{mod}2)$. Upper bound: for $x\ge 2y$ use moves $(2,\pm 1)$, which reach $(2k,\cdot )$ with any $y$ of the right parity up to $k$; for $x<2y$ mix $(2,1)$ and $(1,2)$ moves to reach $(x,y)$ in $\lceil (x+y)/3\rceil$ steps up to a parity fix of one extra move. The construction only fails for tiny offsets, where the knight must step away from the target first; checking all offsets with $x+y\le 6$ (by hand or BFS) leaves exactly the exceptions $(1,0)\to 3$ and $(2,2)\to 4$.

DFS and its timestamps

int timer = 0; vector<int> tin, tout, par;
void dfs(int u, int p, const vector<vector<int>>& g) {     // recursion depth = path length: beware 1e6
    tin[u] = timer++; par[u] = p;
    for (int v : g[u]) if (tin[v] < 0) dfs(v, u, g);
    tout[u] = timer++;
}

Iterative DFS that matches recursive order keeps (vertex, next edge index) on an explicit stack.

Edge $u\to v$ found when scanning $u$	Directed graph	Undirected graph
$v$ unvisited	tree edge	tree edge
$v$ on the current path (grey)	back edge: cycle	back edge: cycle (skip the parent edge by edge id, not vertex, for multigraphs)
$v$ finished, ${\text{tin}}_v>{\text{tin}}_u$	forward edge	impossible
$v$ finished, ${\text{tin}}_v<{\text{tin}}_u$	cross edge	impossible

• $u$ is an ancestor of $v$ iff ${\text{tin}}_u\le {\text{tin}}_v$ and ${\text{tout}}_v\le {\text{tout}}_u$; subtrees are contiguous ranges of $\text{tin}$.
• Topological order = decreasing $\text{tout}$ (Topological Sort).
• Lowlinks give bridges, articulation points and SCCs (Bridges, SCC).
• By itself DFS answers almost nothing; its value is as the skeleton underneath a dozen other algorithms: cycle detection, bipartiteness, topological sort, bridges/articulation points, SCCs, Euler tours, augmenting paths in flows, and maze generation.

Proof: parenthesis and white-path theorems, and the edge classification

Parenthesis: the intervals $[{\text{tin}}_u,{\text{tout}}_u]$ of any two vertices are nested or disjoint, because a call that starts during another call finishes before it (call stack discipline); nested exactly when one is a DFS-tree ancestor of the other.
White path: $v$ becomes a descendant of $u$ iff at time ${\text{tin}}_u$ there is a path from $u$ to $v$ of unvisited (white) vertices. If such a path existed but $v$ were not a descendant, take the first vertex $w$ on the path that isn’t a descendant; its predecessor is a descendant and scans the edge to $w$ before finishing, while $w$ is still white (it can only be discovered inside $u$‘s call), so $w$ would become a descendant, contradiction.
Undirected graphs have no cross/forward edges: when $u$ scans edge $(u,v)$ with $v$ already finished, $v$ must have scanned $(v,u)$ earlier while $u$ was white or grey; if $u$ was white, $u$ would have become $v$‘s descendant, so $u$ was grey and the edge is a back edge from $v$‘s side. Cycle iff back edge: a back edge closes a cycle with the tree path; conversely in a cycle, the first discovered vertex $u$ reaches all others by white paths, so the cycle’s last vertex before $u$ is a descendant of $u$ with an edge to $u$: a back edge.

Connected components and flood fill

DFS/BFS from each unvisited vertex, or DSU when edges arrive online. In directed graphs this gives weakly connected components; for reachability use SCCs. Number of edges to add to connect everything: $c-1$. Grid flood fill is the same on the implicit grid graph (label regions, count islands, area of each region — CSES Counting Rooms, Labyrinth, Monsters).

Situation	Use
static graph, adjacency list ready	DFS/BFS
edges arrive one at a time	DSU
edges are also removed	dynamic connectivity
directed graph	SCC — plain components are the wrong notion
need bridge-resilience	2-edge-connected components
need cut-vertex-resilience	biconnected components