Cycle Detection in Undirected Graph in DSA C# - Time & Space Complexity

Time Complexity: Cycle Detection in Undirected Graph

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to check if an undirected graph has a cycle.

The question is: how does the time grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Detect cycle in undirected graph using DFS
bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach (int neighbor in graph[node]) {
        if (!visited[neighbor]) {
            if (DFS(neighbor, node, graph, visited)) return true;
        } else if (neighbor != parent) {
            return true; // cycle found
        }
    }
    return false;
}

bool HasCycle(List<int>[] graph) {
    int n = graph.Length;
    bool[] visited = new bool[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (DFS(i, -1, graph, visited)) return true;
        }
    }
    return false;
}
    

This code checks if an undirected graph contains a cycle by visiting nodes using depth-first search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node and its neighbors once using DFS recursion.
• How many times: Each edge and node is checked once during the DFS traversal.

How Execution Grows With Input

As the graph grows, the time to check all nodes and edges grows roughly in proportion to the number of nodes plus edges.

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 15 edges	About 25 operations (10 + 15)
100 nodes, 200 edges	About 300 operations (100 + 200)
1000 nodes, 3000 edges	About 4000 operations (1000 + 3000)

Pattern observation: The operations grow linearly with the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time grows linearly with the number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "The DFS will check each edge multiple times, so the time is much higher than linear."

[OK] Correct: Each edge is visited only twice (once from each node), so the total work is proportional to edges plus nodes, not more.

Interview Connect

Understanding this time complexity helps you explain how graph traversal scales and why DFS is efficient for cycle detection.

Self-Check

"What if the graph was directed instead of undirected? How would the time complexity change?"

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 must have 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 during DFS, a visited node is found that is not the parent of the current node, 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 = check visited node not parent [OK]

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

Common Mistakes:

• Ignoring parent node in cycle check
• Assuming disconnected graph always has cycle
• Confusing cycle detection with edge count

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

easy

A. var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>();

B. var graph = new List<int>[3]; graph = new List<int>();

C. List<int> graph = new List<int>[3];

D. var graph = new List(); graph.Add(new List<int>());

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each list initialized separately to hold neighbors.

2. Step 2: Check code correctness

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); creates an array of List<int> and initializes each element with a new List<int>, which is correct.

3. Final Answer:

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); -> Option A

4. Quick Check:

   Initialize array of lists with loop [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using wrong data types for adjacency list
• Assigning list directly to array variable

3. Consider the following C# code snippet for cycle detection in an undirected graph:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else if(neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Graph edges: 0-1, 1-2, 2-0
// Call: DFS(0, -1, graph, visited)

What will be the output of this DFS call?

medium

A. Compilation error

B. false

C. StackOverflowException

D. true

Solution

1. Step 1: Analyze graph structure and DFS call

   The graph has edges 0-1, 1-2, and 2-0 forming a triangle cycle. DFS starts at node 0 with parent -1.

2. Step 2: Trace DFS for cycle detection

   DFS visits 0, then 1, then 2. When 2 checks neighbors, it finds 0 already visited and not parent, so returns true indicating cycle.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Triangle graph cycle detected = true [OK]

Hint: Cycle if visited neighbor not parent found [OK]

Common Mistakes:

• Ignoring parent check causing false cycle
• Assuming no cycle in triangle graph
• Confusing return values in recursion

4. The following C# code attempts to detect a cycle in an undirected graph but has a bug:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else {
            return true;
        }
    }
    return false;
}

What is the bug in this code?

medium

A. It never marks nodes as visited.

B. It returns true even if the visited neighbor is the parent node.

C. It does not traverse all neighbors.

D. It causes infinite recursion.

Solution

1. Step 1: Review cycle detection condition

   The code returns true if a neighbor is visited, but does not check if neighbor is parent.

2. Step 2: Identify why this causes incorrect cycle detection

   In undirected graphs, the parent node is always visited, so returning true here falsely detects a cycle.

3. Final Answer:

   It returns true even if the visited neighbor is the parent node. -> Option B

4. Quick Check:

   Must exclude parent node in cycle check [OK]

Hint: Exclude parent node when checking visited neighbors [OK]

Common Mistakes:

• Missing parent check in visited condition
• Assuming any visited neighbor means cycle
• Not marking nodes visited before recursion

5. You have an undirected graph represented as adjacency list:

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

Using DFS cycle detection, which node will first detect the cycle and why?

hard

A. Node 4, because it has only one neighbor.

B. Node 0, because it starts the DFS traversal.

C. Node 2, because it connects back to already visited node 0.

D. Node 1, because it has the smallest index among neighbors.

Solution

1. Step 1: Understand graph structure and DFS traversal

   Assuming neighbor lists are processed in listed order, DFS starts at node 0, visits 1 (first neighbor), then 3 (from 1), then 2 (from 3).

2. Step 2: Identify where cycle is detected

   Node 2 has neighbors 0 and 3; 0 is already visited and not parent (parent=3), so cycle is detected at node 2 first.

3. Final Answer:

   Node 2, because it connects back to already visited node 0. -> Option C

4. Quick Check:

   Cycle detected at node with visited neighbors not parent [OK]

Hint: Cycle detected where visited neighbors not parent found first [OK]

Common Mistakes:

• Assuming cycle detected at start node
• Ignoring multiple visited neighbors
• Confusing leaf nodes with cycle detection