Cycle Detection in Undirected Graph in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for the graph.

DSA Go

graph := make(map[int][]int)
graph[0] = []int{1, 2}
graph[1] = []int{0, [1]
graph[2] = []int{0}

Drag options to blanks, or click blank then click option'

A3

B2

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing node indices and adding wrong neighbors.

Forgetting that the graph is undirected, so edges go both ways.

Node 1 is connected to nodes 0 and 2, so the adjacency list for node 1 should include 2.

2fill in blank

medium

Complete the code to mark a node as visited in the DFS function.

DSA Go

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

Drag options to blanks, or click blank then click option'

Atrue

Bfalse

Cnil

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited[node] as false instead of true.

Using nil or 0 which are invalid for boolean map values.

We mark the current node as visited by setting visited[node] to true.

3fill in blank

hard

Fix the error in the DFS call inside the cycle detection function.

DSA Go

func hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)
    for node := range graph {
        if !visited[node] {
            if dfs([1], -1, graph, visited) {
                return true
            }
        }
    }
    return false
}

Drag options to blanks, or click blank then click option'

Anode

Bgraph

Cvisited

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Passing the whole graph or visited map instead of a node.

Passing -1 as the starting node.

The DFS should start from the current node in the loop, so the argument is node.

4fill in blank

hard

Fill both blanks to complete the condition that detects a cycle in DFS.

DSA Go

if visited[neighbor] && neighbor != [1] {
    return [2]
}

Drag options to blanks, or click blank then click option'

Aparent

Btrue

Cnode

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning false instead of true when a cycle is found.

Comparing neighbor to node instead of parent.

If a neighbor is visited and is not the parent, it means a cycle is found, so return true.

5fill in blank

hard

Fill all three blanks to complete the main function that builds the graph and checks for cycles.

DSA Go

func main() {
    graph := make(map[int][]int)
    graph[0] = []int{1, [1]
    graph[1] = []int{0, [2]
    graph[2] = []int[3]
    if hasCycle(graph) {
        println("Cycle detected")
    } else {
        println("No cycle")
    }
}

Drag options to blanks, or click blank then click option'

A2

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up neighbors for nodes.

Using wrong indices causing no cycle detection.

Node 0 connects to 1 and 2, node 1 connects to 0 and 1 (which is a self-loop, but here 1 is correct for cycle), node 2 connects to 0.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If all nodes are visited exactly once, there is a cycle.

C. If the graph has more edges than nodes, it always has a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and keeps track of the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found again and it is not the parent, it means a cycle exists.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection in undirected graph = visit visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS [OK]

Common Mistakes:

• Ignoring parent node when checking visited nodes
• Assuming disconnected graph always has cycles
• Confusing cycle detection with number of edges

2. Which of the following Go code snippets correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. graph := make([][]int, 3)
graph[0] = []int{1, 2}
graph[1] = []int{0}
graph[2] = []int{0}

B. graph := make(map[int]int)
graph[0] = 1
graph[1] = 2
graph[2] = 0

C. graph := [][]int{{1, 2}, 0, {0}}

D. graph := make([]int, 3)
graph[0] = 1
graph[1] = 2
graph[2] = 0

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list for an undirected graph is a slice of slices where each index holds neighbors.

2. Step 2: Check code correctness

   graph := make([][]int, 3) graph[0] = []int{1, 2} graph[1] = []int{0} graph[2] = []int{0} correctly creates a slice of slices and assigns neighbors for each node.

3. Final Answer:

   graph := make([][]int, 3) graph[0] = []int{1, 2} graph[1] = []int{0} graph[2] = []int{0} -> Option A

4. Quick Check:

   Adjacency list = slice of slices with neighbors [OK]

Hint: Use [][]int for adjacency list, not map or []int [OK]

Common Mistakes:

• Using map[int]int instead of map[int][]int or [][]int
• Using []int instead of [][]int for adjacency list
• Not initializing slices before assignment

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

package main
import "fmt"

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

func main() {
    graph := [][]int{{1, 2}, {0, 2}, {0, 1}}
    visited := make([]bool, 3)
    if dfs(0, -1, graph, visited) {
        fmt.Println("Cycle detected")
    } else {
        fmt.Println("No cycle")
    }
}

medium

A. Compilation error

B. No cycle

C. Runtime panic

D. Cycle detected

Solution

1. Step 1: Analyze graph structure

   The graph has edges: 0-1, 0-2, and 1-2 forming a triangle, which is a cycle.

2. Step 2: Trace DFS cycle detection

   DFS from node 0 visits 1 and 2; when visiting 2 from 1, it finds 0 already visited and not parent, detecting a cycle.

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Triangle graph = cycle detected [OK]

Hint: Triangle edges always form a cycle [OK]

Common Mistakes:

• Ignoring the neighbor != parent condition
• Assuming no cycle if start node has no parent
• Misreading graph edges

4. Identify the bug in the following Go code for cycle detection in an undirected graph:

func dfs(node int, graph [][]int, visited []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
}

medium

A. Visited array is not initialized

B. Missing parent parameter to avoid false cycle detection

C. Graph adjacency list is incorrectly defined

D. DFS function should return void, not bool

Solution

1. Step 1: Understand DFS cycle detection logic

   In undirected graphs, revisiting a visited node is not always a cycle if it is the parent node.

2. Step 2: Identify missing parent parameter

   The code lacks a parent parameter to exclude the immediate parent from cycle detection, causing false positives.

3. Final Answer:

   Missing parent parameter to avoid false cycle detection -> Option B

4. Quick Check:

   Parent parameter needed to avoid false cycle [OK]

Hint: Always pass parent node in DFS for undirected graphs [OK]

Common Mistakes:

• Not passing parent node in DFS
• Returning true on any visited neighbor
• Confusing directed and undirected cycle detection

5. Given an undirected graph represented as adjacency list:

graph := [][]int{
  {1},
  {0, 2, 3},
  {1, 3},
  {1, 2, 4},
  {3}
}

How many connected components does the graph have and does it contain a cycle?

hard

A. 2 connected components, no cycle

B. 1 connected component, no cycle

C. 1 connected component, contains a cycle

D. 2 connected components, contains a cycle

Solution

1. Step 1: Count connected components

   All nodes 0 to 4 are reachable from each other, so only 1 connected component exists.

2. Step 2: Detect cycle in the graph

   Edges form a cycle among nodes 1, 2, 3 (triangle), so the graph contains a cycle.

3. Final Answer:

   1 connected component, contains a cycle -> Option C

4. Quick Check:

   Single connected graph with triangle cycle [OK]

Hint: Check connectivity then look for triangle cycles [OK]

Common Mistakes:

• Counting connected components incorrectly
• Missing cycle formed by nodes 1, 2, 3
• Assuming no cycle if graph is connected