Graphs and Graph Algorithms Questions

Direct answer

Depth-first search (DFS) with three color states, white (undiscovered), gray (discovered, still being explored on the current path), black (fully finished), detects a directed cycle by recognizing a BACK EDGE: an edge from the node currently being explored into a node that is still gray, meaning still an ancestor on the active exploration path. A back edge means that ancestor depends, directly or transitively, on the very node now trying to reach it, a genuine circular dependency. This is reliable regardless of graph size or shape, including complex, many-branched pipeline dependency graphs, because the gray marker tracks exactly "currently on my path back to the root," which is precisely the condition a cycle requires.

Structured elaboration

The traversal. Start DFS from every white node (covering disconnected components). On visiting a node, mark it gray, then examine each outgoing edge: if the neighbor is white, recurse into it; if the neighbor is gray, a back edge has been found, a cycle; if the neighbor is black, that edge leads to an already-fully-explored subtree reachable some other way, not a cycle. After all of a node's neighbors are processed, mark it black.

Why gray specifically, and not just "visited." A plain boolean visited flag cannot distinguish "still in progress on my current path" from "finished via some completely unrelated path." Consider a diamond shape, $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$: node 3 is reached twice, once via 1 and once via 2, and neither visit is a cycle, since 3 is never an ANCESTOR of either 1 or 2. A boolean visited check alone cannot tell this apart from a genuine cycle case; the three-state color scheme can, because by the time the second path reaches node 3, node 3 has already gone gray to black (fully finished) rather than still being gray, so the algorithm correctly recognizes it as a shared descendant, not a back edge.

Why this is reliable for complex pipeline dependency graphs specifically. A pipeline dependency graph typically has many jobs sharing common upstream stages (many downstream jobs all reading from one shared ingestion stage, for example), which is exactly the diamond shape above at scale. The gray/black distinction is what makes the algorithm correctly ignore all that legitimate sharing while still catching a genuine cycle wherever one exists, independent of how tangled or branching the rest of the graph is, since the check only ever depends on the CURRENT recursion path's gray set, never on the graph's overall shape.

Returning the actual nodes in the detected cycle. Track a parent pointer for every node, set the moment it is first discovered from its immediate predecessor. The instant a back edge $u \to v$ is found ($v$ is gray), walk parent backward starting from $u$ until reaching $v$ itself; that walk, plus $v$ appended again at the end to close the loop, is exactly the cycle, reported as a concrete list of node names rather than a bare "yes, a cycle exists" boolean.

Worked example

def find_cycle(graph):
    color = {v: "white" for v in graph}
    parent = {v: None for v in graph}

    def dfs(u):
        color[u] = "gray"
        for v in graph[u]:
            if color[v] == "white":
                parent[v] = u
                found = dfs(v)
                if found is not None:
                    return found
            elif color[v] == "gray":
                cycle = [v]
                cur = u
                while cur != v:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.append(v)
                cycle.reverse()
                return cycle
        color[u] = "black"
        return None

    for node in graph:
        if color[node] == "white":
            result = dfs(node)
            if result is not None:
                return result
    return None

if __name__ == "__main__":
    dag = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("DAG cycle:", find_cycle(dag))

    pipeline = {"ingest": ["clean"], "clean": ["enrich"], "enrich": ["load"], "load": ["clean"]}
    cyc = find_cycle(pipeline)
    print("Pipeline cycle:", cyc)

    def is_real_cycle(graph, cycle):
        if not cycle or len(cycle) < 2:
            return False
        return all(cycle[i+1] in graph[cycle[i]] for i in range(len(cycle)-1))
    print("Reported pipeline cycle uses only real edges:", is_real_cycle(pipeline, cyc))

    diamond = {0: [1, 2], 1: [3], 2: [3], 3: []}
    print("Diamond (shared descendant, no cycle):", find_cycle(diamond))

Output (actually executed with python3):

DAG cycle: None
Pipeline cycle: ['clean', 'enrich', 'load', 'clean']
Reported pipeline cycle uses only real edges: True
Diamond (shared descendant, no cycle): None

The pipeline example (ingest feeds clean, clean feeds enrich, enrich feeds load, and load mistakenly feeds back into clean) correctly reports the exact cycle ['clean', 'enrich', 'load', 'clean'], verified by an independent edge-by-edge check that every consecutive pair in the reported cycle is a real edge in the original graph, not a fabricated list. The diamond case, structurally similar to the shared-ingestion-stage shape common in real pipelines, correctly reports no cycle at all.

Trade-offs and pitfalls

• Common mistake: returning just the back-edge's two endpoints ($u$ and $v$) as "the cycle," rather than the full path between them. This under-reports the problem: an operator debugging a circular dependency needs to see every job in the loop, not just the two that happened to trigger detection, especially in a pipeline graph where the cycle might span many stages.
• Common mistake: using a plain visited set instead of the three-state scheme and expecting the diamond shape (shared descendant, no actual cycle) to be handled correctly; as shown above, this specific shape is exactly what a boolean check gets wrong, making it a strong test case to include in any cycle-detector's own test suite.
• Multiple independent cycles. This algorithm returns the FIRST cycle it happens to find during its traversal order, not necessarily the "worst" one or all of them; a pipeline validation tool that wants to report every cycle in one pass needs to continue searching after finding one (removing or logging it, then resuming), rather than stopping at the first.
• Self-loops are the degenerate one-node case of exactly the same mechanism: a node pointing to itself is immediately gray when its own edge is examined, correctly detected as a cycle of length one without any special-casing needed.

Direct answer

Iterative deepening depth-first search (IDDFS) repeatedly runs a depth-limited depth-first search (DFS) with an increasing depth cutoff, 0, then 1, then 2, and so on, until the target is found. It combines depth-first search's low memory footprint (proportional to the current depth, not the whole frontier) with breadth-first search (BFS)'s guarantee of finding the shallowest solution first, without paying BFS's memory cost of holding an entire frontier layer in memory at once.

Structured elaboration

Why not just use plain DFS? Plain DFS can dive down an arbitrarily long, wrong branch before ever backtracking to try a shallow, correct one; it offers no guarantee of finding the shortest solution first, and on an infinite or very large search space it might never terminate on a branch that happens to have no solution.

Why not just use plain BFS? BFS does guarantee finding the shallowest solution, but it must hold the entire current frontier in memory, which grows as $O(b^d)$ for branching factor $b$ and depth $d$, the same as IDDFS's TIME complexity, but as memory. For a search space with a large branching factor, that memory requirement becomes the actual bottleneck long before time does.

What IDDFS trades to get both properties. Each depth-limited pass re-does all the work of every shallower pass (visiting depth 0, then 1, then 2 again inside the depth-2 pass, and so on), so IDDFS's total work is more than a single BFS pass, asymptotically the same order, $O(b^d)$, because the geometric sum of work across all depths up to $d$ is dominated by the final, deepest pass. In exchange, memory drops from $O(b^d)$ (BFS) to $O(d)$ (the depth of the current recursion stack), a large practical win whenever memory, not time, is the binding constraint.

Implementation

def iddfs(graph, start, target, max_depth=50):
    '''Iterative deepening DFS: run depth-limited DFS with an increasing depth
    cutoff (0, 1, 2, ...) until target is found or max_depth is exceeded.
    Cycle safety uses PATH membership (the current recursion stack), not a
    global visited set: a global visited set would permanently block a node
    the first time any branch reaches it, even if a different, still-within-
    budget path to the target goes through that same node later in the same
    pass. Returns (path, depth) or (None, None) if not found within max_depth.'''
    for depth_limit in range(max_depth + 1):
        path = [start]
        on_path = {start}
        result = _dls(graph, start, target, depth_limit, path, on_path)
        if result is not None:
            return result, depth_limit
    return None, None

def _dls(graph, node, target, depth_left, path, on_path):
    if node == target:
        return list(path)
    if depth_left <= 0:
        return None
    for nbr in graph.get(node, []):
        if nbr in on_path:
            continue  # avoid cycling back onto our own current path
        path.append(nbr)
        on_path.add(nbr)
        found = _dls(graph, nbr, target, depth_left - 1, path, on_path)
        if found is not None:
            return found
        path.pop()
        on_path.remove(nbr)
    return None

if __name__ == "__main__":
    # Graph WITH a cycle: 0->1->2->3->0, plus a separate branch 1->4->5 (target).
    graph = {0: [1], 1: [2, 4], 2: [3], 3: [0], 4: [5], 5: []}

    path, depth = iddfs(graph, start=0, target=5, max_depth=10)
    print("path to target 5:", path, "found at depth:", depth)
    print("shallowest depth is correct (0->1->4->5 = depth 3):", depth == 3)

    path2, depth2 = iddfs(graph, start=0, target=99, max_depth=6)
    print("unreachable target returns:", path2, depth2)

    path3, depth3 = iddfs(graph, start=2, target=2, max_depth=3)
    print("start==target path:", path3, "depth:", depth3)

    big_cycle = {i: [(i + 1) % 20] for i in range(20)}
    path4, depth4 = iddfs(big_cycle, start=0, target=15, max_depth=25)
    print("20-node ring, 0 to 15 (shortest forward hop count):", depth4, path4 == list(range(16)))

Output (actually executed with python3):

path to target 5: [0, 1, 4, 5] found at depth: 3
shallowest depth is correct (0->1->4->5 = depth 3): True
unreachable target returns: None None
start==target path: [2] depth: 0
20-node ring, 0 to 15 (shortest forward hop count): 15 True

Worked example

Picture a search tree with branching factor $b = 2$ and a solution at depth $d = 3$. IDDFS runs:

• Depth-limited search to depth 0: only the root, no solution, cheap.
• Depth-limited search to depth 1: re-visits the root, then its 2 children, no solution.
• Depth-limited search to depth 2: re-visits depths 0 and 1, then depth 2 (4 nodes), no solution.
• Depth-limited search to depth 3: re-visits depths 0 through 2, then finds the solution among the 8 nodes at depth 3.

Nodes visited across all passes: $1 + (1+2) + (1+2+4) + (1+2+4+8) = 1 + 3 + 7 + 15 = 26$, versus a single BFS pass visiting $1+2+4+8 = 15$ nodes to reach the same depth. The repeated work (26 versus 15) is real but bounded: it is dominated by the final pass's own $1+2+4+8=15$ nodes, so total work stays within a constant factor of a single BFS pass for a fixed branching factor, while memory at any moment never exceeds the current path length (3), not the frontier width (8).

Trade-offs and pitfalls

• When IDDFS is preferable to plain BFS or DFS: the search space is large or its shape (branching factor, depth) is not known ahead of time, a shallow solution is expected or specifically wanted, and memory, not time, is the binding constraint. This is the classic profile of planning and game-tree search under a memory budget.
• When it is not worth it: if the search space is small enough that BFS's memory cost is a non-issue, plain BFS is simpler and does strictly less total work.
• Relation to planning. In state-space planning where the "depth" is plan length, IDDFS corresponds to iterative deepening over plan length: try to find any 0-step plan, then any 1-step plan, and so on, which is exactly the shape needed when the shortest valid plan length is unknown in advance. Combined with a cost heuristic (an estimate of remaining distance to the goal) instead of a plain depth bound, this generalizes to IDA* (iterative-deepening A*), which iterates over an increasing cost threshold rather than a depth threshold.
• Common mistake: forgetting to guard against cycles WITHIN a single depth-limited pass on a graph (as opposed to a tree); without that, a cyclic graph can cause a single depth-limited pass to loop forever within its own depth budget. The guard should be PATH-based (track only the nodes on the current root-to-node branch, as the implementation above does with on_path), not a single global visited set for the whole pass: a global per-pass visited set would permanently block a node the first time ANY branch reaches it, which can wrongly rule out a different, still-within-budget path to the target that happens to pass through that same node later in the same depth-limited pass.
• Common mistake: treating IDDFS's total-work overhead as a memory cost; it is a TIME overhead (redoing shallow work on every pass), not additional memory.

Direct answer

Marking a node visited when it is first DISCOVERED (enqueued, or pushed) versus when it is actually PROCESSED (dequeued, or popped) is not a stylistic choice, it changes correctness. Discovery-time marking guarantees each node enters the frontier exactly once, which is what breadth-first search (BFS) needs for its shortest-path guarantee to hold and what any traversal needs to bound total work to $O(V+E)$. Processing-time marking lets the same node be enqueued multiple times by different discoverers before any of those copies is ever processed, wasting work and, in a concurrent setting, creating a real race.

Structured elaboration

Mark-on-discovery (enqueue/push time). The moment a neighbor is first seen, it is marked visited and added to the frontier, before the algorithm ever looks at it again. Correctness: guarantees each node is scheduled exactly once, since every subsequent discovery of the same node is rejected by the visited check before it can be re-added. Duplicate work: none, by construction. Cycle detection: sufficient for BFS (an infinite loop on a cycle is prevented because a cycle's nodes are never rediscovered), but NOT sufficient on its own for detecting a directed cycle during DFS, since a plain boolean "seen" flag cannot distinguish a node that is still being explored (on the current path) from one that finished long ago. Multi-source: trivial, mark every source visited before the traversal begins, so no source is ever re-added by another source's exploration. Parallel traversals: safer, since the mark-and-claim step happens once, before any work is dispatched, so an atomic compare-and-set on the visited marker is enough to guarantee two workers never both claim the same node.

Mark-on-processing (dequeue/pop time). A node is only marked visited once the algorithm actually gets around to working on it. Correctness: still eventually correct for a simple existence/reachability check, but WRONG for BFS's shortest-path guarantee under certain implementations, since a node can be enqueued multiple times (once per discoverer) before any copy is processed, and depending on queue order, a node might get its distance recorded from a LATER, longer discovery rather than the first, shortest one, if the implementation naively overwrites distance on every dequeue rather than checking a distance already set. Duplicate work: real and often significant, since the same node can sit in the queue multiple times, each copy doing a full "look at my neighbors" pass when eventually processed. Cycle detection: also insufficient alone, for the same white/gray/black reason below. Multi-source: risk of the same node being queued once per source that reaches it, inflating queue size unnecessarily. Parallel traversals: genuinely problematic, since two workers can both see a node as "not yet marked" and both dispatch work on it before either finishes marking it, a textbook race condition requiring an explicit atomic claim step to fix, which mark-on-discovery gets for free by marking BEFORE dispatching any work.

Color states (white, gray, black), the mechanism that fixes what plain marking cannot. White: undiscovered. Gray: discovered, currently being explored (on the active depth-first search path). Black: fully finished, nothing reachable from it remains unexplored. This is strictly more informative than a boolean visited flag: a boolean can only say "seen or not," while color additionally distinguishes "seen and still in progress" from "seen and done." That distinction is exactly what directed-cycle detection needs: encountering an edge into a GRAY node (one still on the current path) means a back edge into an ancestor, a genuine cycle; encountering an edge into a BLACK node means the target was already fully explored via some other path, not a cycle. A plain visited-on-discovery boolean cannot tell these two cases apart, which is why cycle detection specifically needs the three-state version, not merely "was this node marked."

Worked example

Consider a small directed graph: $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$, $3 \to 1$ (a back edge creating the cycle $1 \to 3 \to 1$).

Running DFS from 0 with color states: visit 0 (white to gray), visit 1 (white to gray), visit 3 (white to gray), examine 3's edge to 1: 1 is currently GRAY (still on the active path, 0 to 1 to 3), so this is a back edge, a cycle is correctly reported. Contrast with a plain boolean visited-on-discovery DFS: visit 0 (mark visited), visit 1 (mark visited), visit 3 (mark visited), examine 3's edge to 1: 1 is marked visited, and a naive boolean check alone cannot tell whether that means "1 is an ancestor on my current path" (a cycle) or "1 was already fully explored via some unrelated path" (not a cycle); it would need the color distinction, or an equivalent explicit "currently on stack" set, to tell the two apart correctly.

Trade-offs and pitfalls

• Common mistake: using a plain visited set for DFS cycle detection and expecting it to work like BFS's visited set does. BFS never needs the three-state distinction because BFS has no notion of "still in progress on the current path" the way DFS's call stack does; a boolean is genuinely sufficient there. Porting that same boolean pattern to DFS cycle detection is the single most common source of an "our cycle detector missed a real cycle" or "false-positived on a shared-descendant DAG" bug.
• Common mistake: implementing recursive DFS with a single shared visited set across the whole traversal but forgetting to distinguish "in the current recursion's ancestor chain" from "visited by an earlier, now-finished sibling call." The gray/black split (or an explicit in_progress set that gets removed on backtrack, functionally equivalent) is exactly what an iterative, explicit-stack DFS must also replicate correctly; converting recursive DFS to iterative and dropping this distinction along the way is a real, easy-to-introduce regression.
• Parallel or distributed traversals. Beyond the local correctness question, dispatching work to multiple workers needs the CLAIM step itself to be atomic (a compare-and-set on a shared visited marker, or a lease with an expiry), not merely "check then mark" as two separate, non-atomic operations; two workers can both pass the check before either performs the mark, exactly the race mark-on-discovery avoids only if the mark itself is atomic with respect to the check.
• Recursion-vs-iterative equivalence. A recursive DFS's own call stack implicitly IS the gray set (a node is on the call stack exactly while it is gray); converting to an iterative, explicit-stack version requires either maintaining an explicit gray set alongside the stack or, if the stack contents alone are used as a proxy for "in progress," being careful that a node popped off the explicit stack for backtracking purposes is correctly treated as no longer gray, not still considered in-progress.

Direct answer

Detecting a directed cycle with depth-first search (DFS) and a recursion stack means maintaining two boolean arrays: visited (has this node been explored at all, ever) and inStack (is this node on the CURRENT recursion path right now). An edge into a node that is visited but no longer inStack is harmless, that node was already fully explored via some other path; an edge into a node that IS inStack is a back edge into a live ancestor, a genuine cycle. This runs in $O(V+E)$.

Structured elaboration

visited[u] and inStack[u] are both set the moment DFS enters u. inStack[u] is reset to false the moment DFS finishes exploring everything reachable from u (on backtrack), while visited[u] stays true forever once set. This is what lets the algorithm tell "already explored, but not currently an ancestor" (visited, not inStack, safe) apart from "currently an ancestor on my path" (both visited and inStack, a cycle if reached again).

Worked example

import java.util.*;

public class DirectedCycle {

    public boolean hasCycle(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        boolean[] inStack = new boolean[n];
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                if (dfs(v, graph, visited, inStack)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int u, List<List<Integer>> g, boolean[] visited, boolean[] inStack) {
        visited[u] = true;
        inStack[u] = true;
        for (int v : g.get(u)) {
            if (!visited[v]) {
                if (dfs(v, g, visited, inStack)) return true;
            } else if (inStack[v]) {
                return true; // back edge into a live ancestor
            }
        }
        inStack[u] = false; // backtrack: u is no longer on the active path
        return false;
    }

    // Also returns one concrete cycle as a list of node ids, or an empty list if none exists.
    public List<Integer> findCycle(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        boolean[] inStack = new boolean[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                int[] cycleStart = new int[]{-1};
                if (dfsFind(v, graph, visited, inStack, parent, cycleStart)) {
                    List<Integer> cycle = new ArrayList<>();
                    int cur = cycleStart[0];
                    int start = cur;
                    do {
                        cycle.add(cur);
                        cur = parent[cur];
                    } while (cur != start && cur != -1);
                    cycle.add(start);
                    Collections.reverse(cycle);
                    return cycle;
                }
            }
        }
        return Collections.emptyList();
    }

    private boolean dfsFind(int u, List<List<Integer>> g, boolean[] visited, boolean[] inStack, int[] parent, int[] cycleStart) {
        visited[u] = true;
        inStack[u] = true;
        for (int v : g.get(u)) {
            if (!visited[v]) {
                parent[v] = u;
                if (dfsFind(v, g, visited, inStack, parent, cycleStart)) return true;
            } else if (inStack[v]) {
                parent[v] = u;
                cycleStart[0] = v;
                return true;
            }
        }
        inStack[u] = false;
        return false;
    }

    public static void main(String[] args) {
        DirectedCycle dc = new DirectedCycle();

        List<List<Integer>> acyclic = new ArrayList<>();
        acyclic.add(Arrays.asList(1, 2));
        acyclic.add(Arrays.asList(2));
        acyclic.add(Collections.emptyList());
        System.out.println("Acyclic graph hasCycle: " + dc.hasCycle(3, acyclic));

        List<List<Integer>> cyclic = new ArrayList<>();
        cyclic.add(Arrays.asList(1));
        cyclic.add(Arrays.asList(2));
        cyclic.add(Arrays.asList(0));
        System.out.println("Cyclic graph hasCycle: " + dc.hasCycle(3, cyclic));
        System.out.println("Reconstructed cycle: " + dc.findCycle(3, cyclic));

        List<List<Integer>> disconnected = new ArrayList<>();
        disconnected.add(Arrays.asList(1));
        disconnected.add(Collections.emptyList());
        disconnected.add(Arrays.asList(3));
        disconnected.add(Arrays.asList(2));
        System.out.println("Disconnected graph (cycle in 2nd component) hasCycle: " + dc.hasCycle(4, disconnected));

        List<List<Integer>> selfLoop = new ArrayList<>();
        selfLoop.add(Arrays.asList(0));
        System.out.println("Self-loop hasCycle: " + dc.hasCycle(1, selfLoop));
    }
}

Output (actually compiled and run with javac/java):

Acyclic graph hasCycle: false
Cyclic graph hasCycle: true
Reconstructed cycle: [0, 1, 2, 0]
Disconnected graph (cycle in 2nd component) hasCycle: true
Self-loop hasCycle: true

The disconnected test graph (0 -> 1, no cycle in that component; 2 -> 3 -> 2, a genuine cycle in the second component) confirms the outer loop's for (int v = 0; v < n; v++) if (!visited[v]) correctly restarts DFS from every unvisited node, so a cycle anywhere in the graph is found even if it is not reachable from node 0.

A few points worth naming explicitly about how the two functions above work:

• inStack[u] = true on entry, inStack[u] = false on backtrack: this reset is what makes the distinction between "ancestor, still active" and "already finished elsewhere" possible; forgetting the reset would make every previously-visited node look like a live ancestor forever, turning any two paths into the same node into a false cycle report.
• The single-array visited check alone (without inStack) is exactly what a plain reachability check needs; inStack is the ONLY addition cycle detection requires on top of ordinary DFS.
• findCycle reuses the identical traversal shape, adding only a parent array (set on first discovery) and a cycleStart marker (set the moment a back edge is found), then reconstructs the path by walking parent from the back edge's source back up to the ancestor it points into.

Complexity

Time $O(V+E)$: each vertex is visited once (the visited guard), and each edge is examined exactly once, when its source vertex is processed. Space $O(V)$ for the recursion stack in the worst case (a graph that is one long chain), plus $O(V)$ for the visited, inStack, and (for findCycle) parent arrays.

Edge cases

• Self-loop (a node with an edge to itself): caught immediately, since the node is still inStack (it just entered) when its own edge is examined.
• Disconnected graph with a cycle only in one component: handled correctly by the outer loop restarting DFS from every unvisited node, as demonstrated above.
• Empty graph (n = 0): the outer loop never executes, hasCycle returns false immediately.
• A DAG with a shared descendant (multiple parents pointing to the same child, no actual cycle): correctly reported as no cycle, since by the time the second parent reaches the shared child, that child is visited but no longer inStack (already backtracked out of by the first parent's exploration).

Trade-offs and pitfalls

• Common mistake: forgetting to reset inStack[u] = false on backtrack. Without it, every node ever visited stays permanently marked as "on the stack," and the very next edge into any previously-visited node, cycle or not, would be misreported as a back edge.
• Common mistake: using only visited without inStack and expecting it to work for directed cycle detection; a plain visited check cannot distinguish a live ancestor from an already-finished, unrelated branch, which is exactly the diamond-shaped-DAG false positive this pattern is known to produce.
• Deep, chain-like graphs risk a stack overflow in the recursive Java implementation shown, the same risk an iterative, explicit-stack version avoids; worth naming as a follow-up concern for production code handling untrusted or very deep graphs, distinct from the correctness question this answer is scoped to.
• The findCycle reconstruction variant, returning the actual cycle path rather than a bare boolean, is a natural and common follow-up once the boolean version is understood; it changes nothing about the core traversal logic, only adds the parent/cycleStart bookkeeping needed to recover the path after detection.

Direct answer

Offline dynamic connectivity answers connectivity queries over a graph whose edges are added and removed over time, when the ENTIRE sequence of add/remove/query operations is known in advance. The technique: compute each edge's active time interval from its add and remove operations, place the edge into $O(\log T)$ nodes of a segment tree built over the $T$ discrete time steps (the standard interval-to-segment-tree decomposition), then do a single DFS over the segment tree, applying each node's edges via union on entry and undoing them via rollback on exit, answering every query at its own leaf. This requires a Union-Find variant that supports rollback, which means giving up path compression (path compression's parent rewrites are not cheaply undoable) and relying on union by size or rank alone, which still gives $O(\log n)$ per operation, for a total cost of $O((V + E + Q) \log n \log T)$.

Structured elaboration

Step 1: turn add/remove pairs into intervals. For each edge, scan the operation sequence and pair each "add edge (u,v)" with its matching later "remove edge (u,v)" (or the end of the timeline, if never removed), producing a half-open interval $[\text{start}, \text{end})$ during which that edge is present.

Step 2: decompose each interval onto a segment tree over time. A segment tree with $T$ leaves (one per discrete time step) lets any interval $[\text{start}, \text{end})$ be covered by $O(\log T)$ of the tree's internal nodes (the standard segment-tree range-update decomposition). Store the edge itself at each of those $O(\log T)$ nodes rather than applying it directly, since the edge should only be "active" while the DFS is visiting that subtree's time range.

Step 3: DFS the segment tree with a rollback-capable Union-Find. On entering a tree node, union every edge stored there (tracking exactly what each union did, for undo). Recurse into children. At a LEAF (a single time step), the DSU now reflects exactly the edges active at that instant, so answer every query scheduled for that time step directly. On exiting the node (after both children return), rollback every union performed at that node, in reverse order, restoring the DSU to the state it had before this node was entered. This is what makes the technique correct: each edge's effect is scoped to exactly the time range it was decomposed onto, and rollback removes it cleanly once the DFS moves to a sibling subtree where that edge is not active.

Why path compression cannot be used. Path compression permanently rewrites parent pointers for every node along a find path, and there is no cheap way to remember and reverse all of those rewrites for an undo. Union by size (or rank) alone, WITHOUT path compression, still guarantees $O(\log n)$ tree height, and each union call only changes ONE parent pointer (the smaller root gets reattached under the larger), which is trivially undoable by recording that single pointer change (and the size that was overwritten) and reversing it on rollback.

Worked example

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.history = []

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            self.history.append(None)
            return
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.history.append((ry, self.size[rx]))
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]

    def rollback(self):
        rec = self.history.pop()
        if rec is None:
            return
        child, old_size_of_root = rec
        root = self.parent[child]
        self.parent[child] = child
        self.size[root] = old_size_of_root

    def connected(self, x, y):
        return self.find(x) == self.find(y)


class OfflineDynamicConnectivity:
    def __init__(self, n_nodes, n_time):
        self.n_time = n_time
        self.tree = [[] for _ in range(4 * max(n_time, 1))]
        self.dsu = RollbackDSU(n_nodes)

    def _add(self, node, node_lo, node_hi, lo, hi, edge):
        if hi <= node_lo or node_hi <= lo:
            return
        if lo <= node_lo and node_hi <= hi:
            self.tree[node].append(edge)
            return
        mid = (node_lo + node_hi) // 2
        self._add(2 * node, node_lo, mid, lo, hi, edge)
        self._add(2 * node + 1, mid, node_hi, lo, hi, edge)

    def add_edge(self, u, v, start, end):
        start, end = max(start, 0), min(end, self.n_time)
        if start < end:
            self._add(1, 0, self.n_time, start, end, (u, v))

    def solve(self, queries):
        answers = {t: [] for t in queries}
        self._dfs(1, 0, self.n_time, queries, answers)
        return answers

    def _dfs(self, node, node_lo, node_hi, queries, answers):
        applied = 0
        for (u, v) in self.tree[node]:
            self.dsu.union(u, v)
            applied += 1
        if node_hi - node_lo == 1:
            t = node_lo
            for (u, v) in queries.get(t, []):
                answers[t].append(self.dsu.connected(u, v))
        else:
            mid = (node_lo + node_hi) // 2
            self._dfs(2 * node, node_lo, mid, queries, answers)
            self._dfs(2 * node + 1, mid, node_hi, queries, answers)
        for _ in range(applied):
            self.dsu.rollback()


def brute_force(n_nodes, edges, n_time, queries):
    # Reference: rebuild a fresh DSU from scratch at every time step.
    answers = {t: [] for t in queries}
    for t in range(n_time):
        dsu = RollbackDSU(n_nodes)
        for (u, v, s, e) in edges:
            if s <= t < e:
                dsu.union(u, v)
        for (u, v) in queries.get(t, []):
            answers[t].append(dsu.connected(u, v))
    return answers


if __name__ == "__main__":
    n_nodes, n_time = 5, 6
    # edge (0,1) present during [0,3); (1,2) present during [2,5); (3,4) present [1,6)
    edges = [(0, 1, 0, 3), (1, 2, 2, 5), (3, 4, 1, 6)]
    queries = {
        0: [(0, 1), (0, 2)], 1: [(0, 2)], 2: [(0, 2), (3, 4)],
        3: [(0, 1), (0, 2)], 4: [(1, 2)], 5: [(1, 2), (3, 4)],
    }

    odc = OfflineDynamicConnectivity(n_nodes, n_time)
    for (u, v, s, e) in edges:
        odc.add_edge(u, v, s, e)
    fast_answers = odc.solve(queries)
    ref_answers = brute_force(n_nodes, edges, n_time, queries)

    print("time  fast            brute")
    for t in range(n_time):
        print(t, fast_answers.get(t, []), ref_answers.get(t, []))
    print("MATCH:", fast_answers == ref_answers)

Output:

time  fast            brute
0 [True, False] [True, False]
1 [False] [False]
2 [True, True] [True, True]
3 [False, False] [False, False]
4 [True] [True]
5 [False, True] [False, True]
MATCH: True

Every time step's answers from the segment-tree-plus-rollback approach exactly match a brute-force reference that rebuilds a fresh DSU from scratch at every single time step, confirming the rollback bookkeeping correctly scopes each edge to only its active interval.

Trade-offs and pitfalls

• This technique is OFFLINE by definition: it needs every add, remove, and query operation known before processing starts, because the interval decomposition in step 1 requires knowing an edge's remove time (or the timeline's end) at the moment it is added. It cannot answer a query against a live, still-growing stream.
• Memory: $O((E + Q) \log T)$ for the segment tree's stored edges across all $O(\log T)$ nodes per edge, plus $O(V)$ for the DSU itself; this is larger than plain Union-Find's $O(V)$ footprint, the price paid for supporting the full add/remove/query timeline in one pass.
• Common mistake: using path compression anyway "for speed," which silently breaks rollback correctness. Path compression's rewrites are not tracked by this rollback scheme; adding it back would require also tracking and reversing every compressed pointer, which erases the whole point of choosing union-by-size-only in the first place.
• Common mistake: forgetting to roll back in the exact reverse order unions were applied at a node, especially when a node has more than one edge; since later unions can depend on the tree shape earlier unions produced, rollback must be last-in-first-out (a stack, as used here), never applied in insertion order or in bulk without respecting that order.