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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

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

DSA Go

package main

import "fmt"

func dfs(node int, graph map[int][]int, visited, recStack map[int]bool) bool {
    visited[node] = true
    recStack[node] = true

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, graph, visited, recStack) {
                return true
            }
        } else if recStack[neighbor] {
            return true
        }
    }

    recStack[node] = false
    return false
}

func hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)
    recStack := make(map[int]bool)

    for node := range graph {
        if !visited[node] {
            if dfs(node, graph, visited, recStack) {
                return true
            }
        }
    }
    return false
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {4},
        4: {2},
    }
    fmt.Println(hasCycle(graph))
}

A Compilation error

B false

C true

D panic: runtime error

💡 Hint

Think about whether the graph has a back edge that forms a cycle.

The graph has edges 1->2, 2->3, 3->4, and 4->2. The edge 4->2 creates a cycle involving nodes 2, 3, and 4. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Output of cycle detection with no cycle

What is the output of this Go code that checks for a cycle in a directed graph with no cycles?

DSA Go

package main

import "fmt"

func dfs(node int, graph map[int][]int, visited, recStack map[int]bool) bool {
    visited[node] = true
    recStack[node] = true

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, graph, visited, recStack) {
                return true
            }
        } else if recStack[neighbor] {
            return true
        }
    }

    recStack[node] = false
    return false
}

func hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)
    recStack := make(map[int]bool)

    for node := range graph {
        if !visited[node] {
            if dfs(node, graph, visited, recStack) {
                return true
            }
        }
    }
    return false
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {4},
        4: {},
    }
    fmt.Println(hasCycle(graph))
}

A false

B true

C Compilation error

D panic: runtime error

💡 Hint

Check if any node leads back to an ancestor in the recursion stack.

The graph edges are 1->2, 2->3, 3->4, and 4 has no outgoing edges. There is no cycle, so the function returns false.

🔧 Debug

advanced

Identify the error in cycle detection code

What error does this Go code produce when detecting cycles in a directed graph?

DSA Go

package main

import "fmt"

func dfs(node int, graph map[int][]int, visited map[int]bool) bool {
    visited[node] = true

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, graph, visited) {
                return true
            }
        } else {
            return true
        }
    }

    return false
}

func hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)

    for node := range graph {
        if !visited[node] {
            if dfs(node, graph, visited) {
                return true
            }
        }
    }
    return false
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {1},
    }
    fmt.Println(hasCycle(graph))
}

A false

B Stack overflow runtime error

C Compilation error

D true

💡 Hint

Check if the code uses a recursion stack to detect back edges.

The code lacks a recursion stack to differentiate between nodes currently in the recursion path and fully visited nodes. However, in this graph, the cycle 1->2->3->1 is detected because a visited neighbor is found during DFS, so it returns true.

🧠 Conceptual

advanced

Why use recursion stack in cycle detection?

Why is a recursion stack (or call stack tracking) needed in DFS-based cycle detection in directed graphs?

A To detect back edges indicating a cycle in the current DFS path

B To detect if a node is visited for the first time

C To store all nodes in the graph for traversal

D To avoid visiting nodes multiple times

💡 Hint

Think about how cycles appear in DFS traversal.

The recursion stack helps identify back edges, which are edges pointing to nodes currently in the recursion path. These back edges indicate a cycle in directed graphs.

🚀 Application

expert

Number of cycles in a directed graph

Given the following directed graph, how many distinct cycles does it contain? Edges: 1 -> 2 2 -> 3 3 -> 1 3 -> 4 4 -> 5 5 -> 3 6 -> 7 7 -> 6

A 2

B 3

C 1

D 4

💡 Hint

Identify all unique cycles formed by edges.

There are three distinct cycles:
1) 1 -> 2 -> 3 -> 1
2) 3 -> 4 -> 5 -> 3
3) 6 -> 7 -> 6

Practice

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

easy

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

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

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 A

4. Quick Check:

   Cycle detection = finding directed loops [OK]

Hint: Cycle means a loop following edge directions [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly declares a graph as an adjacency list for cycle detection?

easy

A. graph := make(map[int][]int)

B. graph := []int{}

C. graph := map[int]int{}

D. graph := [][]int{}

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list for a directed graph maps each node to a list of nodes it points to.

2. Step 2: Check Go syntax for adjacency list

   Using map[int][]int creates a map from int to slice of ints, perfect for adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Adjacency list = map[int][]int [OK]

Hint: Adjacency list uses map of int to slice of int [OK]

Common Mistakes:

• Using slice of int only (no mapping)
• Using map[int]int which stores single int per node
• Using [][]int without map keys

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

package main
import "fmt"

func dfs(node int, graph map[int][]int, visited, recStack map[int]bool) bool {
    if recStack[node] {
        return true
    }
    if visited[node] {
        return false
    }
    visited[node] = true
    recStack[node] = true
    for _, neighbor := range graph[node] {
        if dfs(neighbor, graph, visited, recStack) {
            return true
        }
    }
    recStack[node] = false
    return false
}

func main() {
    graph := map[int][]int{
        1: {2},
        2: {3},
        3: {1},
    }
    visited := make(map[int]bool)
    recStack := make(map[int]bool)
    fmt.Println(dfs(1, graph, visited, recStack))
}

medium

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze graph structure

   Graph edges: 1->2, 2->3, 3->1 form a cycle.

2. Step 2: Trace DFS cycle detection

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

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle detected = true [OK]

Hint: Cycle if node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming visited alone detects cycle
• Confusing false with no cycle

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

func dfs(node int, graph map[int][]int, visited map[int]bool) bool {
    if visited[node] {
        return true
    }
    visited[node] = true
    for _, neighbor := range graph[node] {
        if dfs(neighbor, graph, visited) {
            return true
        }
    }
    return false
}

medium

A. Return type should be int, not bool

B. Visited map should be a slice, not a map

C. Missing recursion stack to track nodes in current path

D. Graph should be a slice of slices, not a map

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path (recursion stack).

2. Step 2: Identify missing recursion stack

   This code only uses visited to mark visited nodes, which cannot detect cycles correctly in directed graphs.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for directed cycle detection [OK]

Hint: Use recursion stack to detect back edges [OK]

Common Mistakes:

• Using only visited to detect cycles
• Confusing undirected and directed cycle detection
• Ignoring recursion stack leads to false negatives

5. Given a directed graph represented as adjacency list:

graph := map[int][]int{
    1: {2, 3},
    2: {4},
    3: {4, 5},
    4: {6},
    5: {6},
    6: {3},
}

Which nodes are part of a cycle in this graph?

hard

A. [1, 3, 5]

B. [1, 2, 5]

C. [2, 4, 5]

D. [3, 4, 6]

Solution

1. Step 1: Analyze edges for cycles

   Edges: 3->4, 4->6, 6->3 form a cycle involving nodes 3, 4, 6.

2. Step 2: Confirm cycle nodes

   Nodes 1, 2, 5 lead into cycle but are not part of cycle themselves.

3. Final Answer:

   [3, 4, 6] -> Option D

4. Quick Check:

   Cycle nodes = [3,4,6] [OK]

Hint: Trace back edges to find cycle nodes [OK]

Common Mistakes:

• Including nodes that only lead to cycle
• Missing nodes that form the cycle
• Confusing cycle membership with reachability