Exercises — DFS applications — cycle detection (directed and undirected)

No cycle. It is a straight path — nobody points back. DFS from $A$: paint $A,B,C,D$ Gray one after another, hit no Gray neighbour, then finish them back up so all four end Black. A finished (Black) chain with no back edge = acyclic.

Cycle. It is a triangle. Walking $A\to B\to C$, from $C$ we see neighbour $A$ which is visited and not the parent ($B$). The edge $C-A$ closes the loop.

Yes — the smallest possible directed cycle. Enter $A$, paint it Gray, scan its neighbours, find $A$ itself which is currently Gray → back edge → cycle immediately.

• dfs(A): A=Gray. Try $B$.
• dfs(B): B=Gray. Try $C$.
• dfs(C): C=Gray. Neighbour $B$ is Gray → back edge $C\to B$ → cycle = True.

The 2-cycle $B\to C\to B$ is the culprit.

• dfs(A,-1): visit A → go $B$.
• dfs(B,A): visit B → skip parent $A$ → go $C$.
• dfs(C,B): visit C → skip parent $B$ → go $D$.
• dfs(D,C): visit D → parent is $C$ (skip). Neighbour $B$ is visited and $\ne$ parent $C$ → cycle = True.

Closing edge: $D-B$. The loop is $B-C-D-B$.

No cycle. From $A$ we visit each leaf; each leaf's only neighbour is $A$ = its parent = skipped. A star on $5$ nodes has $4=n-1$ edges → it is a tree → acyclic.

Their buggy dfs(u,parent) ignores any visited neighbour equal to parent:

• dfs(A,-1): visit A → go $B$.
• dfs(B,A): visit B → neighbour $A$ is visited and equals parent → skipped → returns no cycle.

Wrong. The true graph has the 2-cycle $A\to B\to A$. The parent-skip erased exactly the edge that proves it. Correct verdict: cycle exists. Directed edges are not symmetric, so there is no "spurious reverse copy" to forgive — the edge $B\to A$ is a genuine distinct arrow. Use 3 colours instead; $B$ sees $A$ still Gray → back edge.

Two parallel edges $A=B$ are a cycle (go out on edge 1, come back on edge 2). But plain parent-skip fails:

• dfs(A,-1): visit A → go $B$ via edge 1.
• dfs(B,A): visit B → scan neighbours: $A$ (via edge 2) is visited but equals parent → skipped. Missed!

Fix: track the edge index you arrived on, not just the parent vertex. Then edge 2 ($\ne$ arrival edge) is recognised as a genuine return route → cycle. (See figure below.)

A forest (acyclic undirected graph) with $n$ nodes and $c$ connected pieces has exactly $n-c$ edges. Since $c\ge 1$, a forest has at most $n-1$ edges. We have $n$ edges $>n-1$, so the graph is not a forest → it contains a cycle. (Equivalently: run DFS; with $n$ edges but only $n-1$ tree edges possible, at least one edge is a back edge.)

A topological order exists iff the graph is a DAG (no directed cycle). DFS-based topo sort emits nodes in decreasing finish time. If during that DFS you ever find an edge to a Gray node — a back edge — a directed cycle exists, so no valid ordering exists and topo sort must fail/report the cycle. So the same Gray-check is the acyclicity gatekeeper. See Back Edges and Edge Classification for why only back edges (not forward/cross) signal cycles.

Triangle $A-B$, $B-C$, $C-A$.

• DFS: discovers the cycle when, deep in recursion at $C$, it sees visited non-parent $A$ (edge $C-A$).
• DSU: processes edges one at a time. It unions $\{A,B\}$, then $\{A,B,C\}$ (via $B-C$). When it reaches $C-A$, both endpoints are already in the same set → cycle. Same closing edge $C-A$, but DSU never traverses depth — it just asks "are these two already connected?" DSU shines when you only have an edge list and no need for traversal order.

False. No directed cycle just means the graph is a DAG; it says nothing about 2-colourability. Bipartiteness is about odd-length undirected cycles and is tested with Bipartite Checking (2-colour DFS/BFS on the undirected view). A DAG like $A\to B$, $A\to C$, $B\to C$ has an odd undirected cycle-free structure here, but in general acyclic-directed and bipartite are unrelated properties. Different question → different tool.

Keep color[] and a parent[] (who called us). Run the standard 3-colour DFS. The moment dfs(u) finds a neighbour v that is Gray, you have the back edge $u\to v$. Reconstruct the cycle by walking parent[] from u back up until you reach v, then append v:

cycle = [u]
x = u
while x != v:
    x = parent[x]
    cycle.append(x)
reverse(cycle)   # now v ... u, plus the edge u->v closes it

Invariant: at any instant the set of Gray nodes forms exactly the current recursion path (a simple chain via parent[]), so walking parent[] from u up to the Gray ancestor v traces a real path, and the back edge $u\to v$ closes it into a genuine cycle. Complexity: still $O(V+E)$ for the DFS; the reconstruction walk is $O(\text{cycle length})\le O(V)$, absorbed into the total.

for u in all_vertices:
    if color[u] == WHITE:
        if dfs(u): return True      # dfs is the 3-colour version
return False

Never misses: every White vertex eventually starts a DFS (the driver loop), and every edge out of a Gray vertex is scanned, so any back edge — including a self-loop $u\to u$ caught while $u$ is Gray — is seen. Never false-alarms: we only return True on a Gray neighbour; a Gray neighbour is provably still on the stack (an ancestor), so a real directed path exists from it down to the current node, and the edge back to it closes a real cycle. Black neighbours (finished) are skipped, correctly ignoring forward/cross edges. Complexity: $O(V+E)$ time, $O(V)$ space.

Connected + acyclic = a tree, so it has $V-1=5$ edges. Adding one edge between two already-connected tree nodes creates exactly one simple cycle: the unique tree path between the endpoints, plus the new edge. So: 5 edges, and adding one gives 1 new simple cycle.

"In directed graphs a cycle is a live back edge (neighbour still Gray); in undirected graphs a cycle is a visited non-parent neighbour (track the edge if the graph is a multigraph) — and always loop over every component."