Depth-First Search: Parenthesis Theorem, White-Path Theorem & Tree/Back/Forward/Cross Edges

Temporal Coordinate System & The Three-Color Invariant

During a DFS traversal of a directed or undirected graph $G = (V, E)$, every vertex $u \in V$ transitions monotonically through three states:

• WHITE ($0$): Undiscovered ($t < \text{tin}[u]$).
• GRAY ($1$): Discovered and currently active on the recursion stack ($\text{tin}[u] \le t < \text{tout}[u]$). The set of all GRAY vertices at any instant forms the exact path from the current DFS root to the currently executing vertex.
• BLACK ($2$): Fully explored and popped from the recursion stack ($t \ge \text{tout}[u]$).

Complete Classification of Directed & Undirected Edges

When DFS at vertex $u$ inspects an outgoing edge $(u, v)$, the color and timestamps of $v$ classify $(u, v)$ into one of four mutually exclusive categories:

1. Tree Edge: $v$ is WHITE at inspection time. DFS recurses on $v$, making $u$ the tree parent of $v$.
2. Back Edge: $v$ is GRAY at inspection time ($\text{tin}[v] \le \text{tin}[u]$ and $\text{tout}[v]$ is not yet assigned). Thus $v$ is an active ancestor of $u$ on the call stack. A directed graph has a cycle if and only if a DFS yields at least one back edge.
3. Forward Edge: $v$ is BLACK at inspection time and $\text{tin}[u] < \text{tin}[v]$. Here $v$ is a proper descendant of $u$ that was already visited via another tree branch.
4. Cross Edge: $v$ is BLACK at inspection time and $\text{tin}[v] < \text{tout}[v] < \text{tin}[u]$. The intervals $I_u$ and $I_v$ are disjoint.

Crucial Undirected Graph Theorem: In an undirected simple graph $G$, every edge is either a Tree Edge or a Back Edge. Forward and cross edges cannot exist because if ${u, v}$ is first explored from whichever endpoint is discovered earlier (say $u$), $v$ is still WHITE or GRAY; it can never be BLACK before ${u, v}$ is traversed.

Complexity Matrix

Production Implementation: Iterative DFS with Timestamps & Cycle Reconstruction

#include <vector>
#include <algorithm>

struct DFSTimestamps {
    std::vector<int> tin, tout, parent;
    std::vector<uint8_t> color; // 0=WHITE, 1=GRAY, 2=BLACK
    std::vector<int> cycle;
    int timer = 0;

    DFSTimestamps(int n, const std::vector<std::vector<int>>& adj)
        : tin(n, 0), tout(n, 0), parent(n, -1), color(n, 0) {
        struct Frame { int u; size_t edgeIdx; };
        std::vector<Frame> st;
        st.reserve(n);

        for (int root = 0; root < n; ++root) {
            if (color[root] != 0) continue;
            color[root] = 1;
            tin[root] = ++timer;
            st.push_back({root, 0});

            while (!st.empty()) {
                auto& [u, idx] = st.back();
                if (idx < adj[u].size()) {
                    int v = adj[u][idx++];
                    if (color[v] == 0) {
                        parent[v] = u;
                        color[v] = 1;
                        tin[v] = ++timer;
                        st.push_back({v, 0});
                    } else if (color[v] == 1 && cycle.empty()) {
                        // Back edge u -> v detected; reconstruct directed cycle
                        for (int cur = u; cur != v; cur = parent[cur]) {
                            cycle.push_back(cur);
                        }
                        cycle.push_back(v);
                        std::reverse(cycle.begin(), cycle.end());
                    }
                } else {
                    color[u] = 2;
                    tout[u] = ++timer;
                    st.pop_back();
                }
            }
        }
    }

    bool isAncestor(int u, int v) const noexcept {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }
};