Cycle Detection in Directed Graph in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following Java code that detects a cycle in a directed graph using DFS?

DSA Java

import java.util.*;

public class GraphCycle {
    private final int V;
    private final List<List<Integer>> adj;

    public GraphCycle(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor] && dfs(neighbor, visited, recStack)) {
                return true;
            } else if (recStack[neighbor]) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle(4);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        System.out.println(graph.hasCycle());
    }
}

A Runtime exception

B false

C true

D Compilation error

💡 Hint

Trace the DFS recursion and check if any node is revisited in the current recursion stack.

The graph has a cycle: 1 -> 2 -> 3 -> 1. The DFS detects this cycle by tracking nodes in the recursion stack, so the output is true.

❓ Predict Output

intermediate

Output of cycle detection with no cycle

What is the output of the following Java code that detects a cycle in a directed graph with no cycles?

DSA Java

import java.util.*;

public class GraphCycle {
    private final int V;
    private final List<List<Integer>> adj;

    public GraphCycle(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor] && dfs(neighbor, visited, recStack)) {
                return true;
            } else if (recStack[neighbor]) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle(3);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);

        System.out.println(graph.hasCycle());
    }
}

A false

B Compilation error

C true

D Runtime exception

💡 Hint

Check if any node is revisited in the current recursion stack during DFS.

The graph has no cycle. The DFS completes without finding any back edge, so the output is false.

🔧 Debug

advanced

Identify the error in cycle detection code

What error will the following Java code produce when detecting a cycle in a directed graph?

DSA Java

import java.util.*;

public class GraphCycle {
    private final int V;
    private final List<List<Integer>> adj;

    public GraphCycle(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {  // Note the <= here
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor] && dfs(neighbor, visited, recStack)) {
                return true;
            } else if (recStack[neighbor]) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle(3);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);

        System.out.println(graph.hasCycle());
    }
}

A NullPointerException

B ArrayIndexOutOfBoundsException

C StackOverflowError

D No error, prints true

💡 Hint

Check the loop that initializes adjacency lists and the size of arrays used.

The adjacency list is initialized with V lists but the original code had <= V which caused one extra list. Here fixed to < V. The visited and recStack arrays have size V. Accessing adj.get(V) causes ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Why use recursion stack in cycle detection?

In cycle detection for directed graphs using DFS, why do we maintain a recursion stack (recStack) array alongside the visited array?

A To mark nodes that have been fully processed and can be skipped

B To store the order of nodes visited for topological sorting

C To count the number of neighbors each node has

D To track nodes currently in the recursion path to detect back edges indicating cycles

💡 Hint

Think about how a cycle is detected during DFS traversal in a directed graph.

The recursion stack tracks nodes in the current DFS path. If we revisit a node in this stack, it means a cycle exists (a back edge).

🚀 Application

expert

Detect cycle in a complex directed graph

Given the following directed graph edges, which option correctly shows the output of the cycle detection code?

DSA Java

import java.util.*;

public class GraphCycle {
    private final int V;
    private final List<List<Integer>> adj;

    public GraphCycle(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    private boolean dfs(int node, boolean[] visited, boolean[] recStack) {
        visited[node] = true;
        recStack[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor] && dfs(neighbor, visited, recStack)) {
                return true;
            } else if (recStack[neighbor]) {
                return true;
            }
        }

        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        boolean[] visited = new boolean[V];
        boolean[] recStack = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, recStack)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle(6);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        graph.addEdge(5, 3);

        System.out.println(graph.hasCycle());
    }
}

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Look for a cycle involving nodes 3, 4, and 5.

The graph contains a cycle: 3 -> 4 -> 5 -> 3. The DFS detects this cycle and returns true.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. The maximum degree of any node

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. Whether there is a path that starts and ends at the same node following the direction of edges

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following edge directions.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following the direction of edges -> Option D

4. Quick Check:

   Cycle detection = finding directed cycles [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which Java data structure is commonly used to keep track of nodes currently in the recursion stack during DFS for cycle detection?

easy

A. Stack

B. HashSet

C. Queue

D. ArrayList

Solution

1. Step 1: Identify recursion stack tracking

   During DFS, nodes in the current path are tracked to detect back edges indicating cycles.

2. Step 2: Choose suitable data structure

   A HashSet is used to quickly check if a node is in the current recursion stack.

3. Final Answer:

   HashSet -> Option B

4. Quick Check:

   Use HashSet to track recursion stack nodes [OK]

Hint: Use HashSet for O(1) check if node is in recursion stack [OK]

Common Mistakes:

• Using Queue which is FIFO, not suitable here
• Using Stack but not checking membership efficiently
• Using ArrayList which is slower for membership check

3. What will be the output of the following Java code snippet detecting cycle in a directed graph?

import java.util.*;

public class GraphCycle {
    private final int V = 3;
    private final List adj = new ArrayList<>();
    private final boolean[] visited = new boolean[V];
    private final boolean[] recStack = new boolean[V];

    public GraphCycle() {
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        adj.get(0).add(1);
        adj.get(1).add(2);
        adj.get(2).add(0);
    }

    private boolean dfs(int node) {
        if (recStack[node]) return true;
        if (visited[node]) return false;
        visited[node] = true;
        recStack[node] = true;
        for (int neighbor : adj.get(node)) {
            if (dfs(neighbor)) return true;
        }
        recStack[node] = false;
        return false;
    }

    public boolean hasCycle() {
        for (int i = 0; i < V; i++) {
            if (dfs(i)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        GraphCycle graph = new GraphCycle();
        System.out.println(graph.hasCycle());
    }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze graph edges

   Edges: 0->1, 1->2, 2->0 form a cycle (0->1->2->0).

2. Step 2: Trace DFS cycle detection

   DFS from node 0 visits 1, then 2, then back to 0 which is in recursion stack, so returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists in graph = true [OK]

Hint: Cycle if DFS revisits node in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle because visited[] is true
• Confusing visited[] and recStack[] roles

4. Identify the bug in this cycle detection code snippet for a directed graph:

boolean dfs(int node, boolean[] visited, boolean[] recStack, List adj) {
    visited[node] = true;
    recStack[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, recStack, adj);
        } else if (recStack[neighbor]) {
            return true;
        }
    }
    recStack[node] = false;
    return false;
}

medium

A. Loop iterates over wrong adjacency list

B. recStack is not reset to false

C. Missing return statement in recursive call

D. visited array is not updated

Solution

1. Step 1: Check recursive call handling

   Recursive call dfs(neighbor, ...) is made but its return value is ignored.

2. Step 2: Understand impact on cycle detection

   If dfs(neighbor) returns true (cycle found), this should be returned immediately to propagate detection.

3. Final Answer:

   Missing return statement in recursive call -> Option C

4. Quick Check:

   Return recursive call result to detect cycles [OK]

Hint: Return recursive dfs result to catch cycles early [OK]

Common Mistakes:

• Ignoring return value of recursive dfs
• Not resetting recStack[node] to false
• Confusing visited and recStack roles

5. Given a directed graph represented as adjacency list:

{
  0: [1],
  1: [2],
  2: [3],
  3: [1, 4],
  4: []
}

Which nodes are part of at least one cycle?

hard

A. [1, 2, 3]

B. [0, 1, 2, 3]

C. [1, 3]

D. [0, 4]

Solution

1. Step 1: Identify cycles in graph

   Edges: 1->2, 2->3, 3->1 form a cycle involving nodes 1, 2, 3.

2. Step 2: Check other nodes

   Node 0 points to 1 but is not in cycle; node 4 has no outgoing edges.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Cycle nodes = [1, 2, 3] [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes that only lead to cycle but not in it
• Missing nodes inside the cycle
• Confusing cycle presence with reachability