Cycle Detection in Undirected Graph in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection on a simple graph

What is the output of the following C++ code that detects a cycle in an undirected graph?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, adj, visited)) return true;
        }
    }
    return false;
}

int main() {
    int V = 4;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {0, 2};
    adj[2] = {0, 1, 3};
    adj[3] = {2};
    cout << (hasCycle(V, adj) ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

A Cycle detected

B No cycle

C Compilation error

D Runtime error

💡 Hint

Check if any back edge exists in the undirected graph.

The graph contains a cycle between nodes 0, 1, and 2. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Cycle detection output on a tree graph

What will be printed by this C++ code that checks for cycles in an undirected graph structured as a tree?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, adj, visited)) return true;
        }
    }
    return false;
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {0};
    adj[2] = {0, 3, 4};
    adj[3] = {2};
    adj[4] = {2};
    cout << (hasCycle(V, adj) ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

A Cycle detected

B Runtime error

C Compilation error

D No cycle

💡 Hint

A tree has no cycles by definition.

The graph is a tree structure with no cycles, so the DFS never finds a back edge and returns false.

🔧 Debug

advanced

Identify the bug causing incorrect cycle detection

The following code is intended to detect cycles in an undirected graph but always returns "Cycle detected" even when no cycle exists. What is the bug?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor == parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, adj, visited)) return true;
        }
    }
    return false;
}

int main() {
    int V = 3;
    vector<vector<int>> adj(V);
    adj[0] = {1};
    adj[1] = {0, 2};
    adj[2] = {1};
    cout << (hasCycle(V, adj) ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

A The condition 'neighbor == parent' should be 'neighbor != parent' to detect cycles correctly.

B The visited array is not initialized properly.

C The adjacency list is missing edges.

D The DFS function should not mark nodes as visited.

💡 Hint

Check the logic that detects a back edge in DFS.

The code incorrectly returns true when neighbor equals parent, which is the opposite of the correct logic. It should return true when neighbor is visited and not the parent.

🧠 Conceptual

advanced

Why does DFS detect cycles in undirected graphs?

Which statement best explains why DFS can detect cycles in an undirected graph?

A DFS detects a cycle by counting the number of edges and vertices.

B DFS detects a cycle when it visits all nodes without revisiting any node.

C DFS detects a cycle when it finds a visited node that is not the parent of the current node.

D DFS detects a cycle only if the graph is directed.

💡 Hint

Think about what a back edge means in DFS for undirected graphs.

In undirected graphs, a cycle exists if DFS finds a visited node that is not the parent, indicating a back edge.

❓ Predict Output

expert

Output of cycle detection on disconnected graph with multiple components

What is the output of the following C++ code that detects cycles in an undirected graph with two disconnected components, one with a cycle and one without?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, adj, visited)) return true;
        }
    }
    return false;
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    // Component 1 with cycle: 0-1-2-0
    adj[0] = {1, 2};
    adj[1] = {0, 2};
    adj[2] = {0, 1};
    // Component 2 without cycle: 3-4-5
    adj[3] = {4};
    adj[4] = {3, 5};
    adj[5] = {4};
    cout << (hasCycle(V, adj) ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

A No cycle

B Cycle detected

C Compilation error

D Runtime error

💡 Hint

Check all disconnected components for cycles.

The first component contains a cycle, so the function returns true even though the second component has no cycle.

Practice

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

easy

A. If all nodes are visited once, the graph has a cycle.

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

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 tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

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

4. Quick Check:

   Cycle detection in undirected graph = check visited and parent [OK]

Hint: Check visited nodes excluding parent to find cycles [OK]

Common Mistakes:

• Ignoring the parent node in cycle check
• Assuming disconnected graph always has cycles
• Confusing cycle detection with number of edges

2. Which of the following C++ function signatures is correct for a DFS-based cycle detection helper in an undirected graph?

easy

A. bool dfs(int node, int parent, vector& graph, vector<bool>& visited);

B. void dfs(int node, vector<int>& graph, vector<bool>& visited);

C. bool dfs(int node, vector<int>& graph, vector<int>& visited, int parent);

D. int dfs(int node, int parent, vector<int>& graph, vector<bool>& visited);

Solution

1. Step 1: Analyze function parameters for DFS cycle detection

   We need current node, parent node, adjacency list (graph), and visited array.

2. Step 2: Check return type and parameter types

   Return type should be bool to indicate cycle presence; graph is vector of vectors; visited is bool vector.

3. Final Answer:

   bool dfs(int node, int parent, vector& graph, vector<bool>& visited); -> Option A

4. Quick Check:

   Correct DFS signature includes parent and returns bool [OK]

Hint: DFS cycle helper returns bool and takes parent node [OK]

Common Mistakes:

• Using wrong graph data type (vector<int> instead of vector)
• Missing parent parameter
• Wrong return type for cycle detection

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

int main() {
  vector graph = {{1,2}, {0,2}, {0,1,3}, {2}};
  vector<bool> visited(4, false);
  bool hasCycle = false;
  function dfs = [&](int node, int parent) {
    visited[node] = true;
    for (int adj : graph[node]) {
      if (!visited[adj]) {
        if (dfs(adj, node)) return true;
      } else if (adj != parent) {
        return true;
      }
    }
    return false;
  };
  for (int i = 0; i < 4; i++) {
    if (!visited[i]) {
      if (dfs(i, -1)) {
        hasCycle = true;
        break;
      }
    }
  }
  cout << (hasCycle ? "Cycle Found" : "No Cycle") << endl;
  return 0;
}

medium

A. Runtime Error

B. No Cycle

C. Compilation Error

D. Cycle Found

Solution

1. Step 1: Analyze graph structure

   Graph edges: 0-1, 0-2, 1-2, 2-3. Nodes 0,1,2 form a triangle (cycle).

2. Step 2: Trace DFS cycle detection

   DFS visits nodes and finds back edge between 0 and 2 or 1 and 2, detecting cycle.

3. Final Answer:

   Cycle Found -> Option D

4. Quick Check:

   Triangle in graph means cycle detected [OK]

Hint: Triangle or more edges among nodes means cycle [OK]

Common Mistakes:

• Ignoring back edge condition
• Assuming no cycle if graph is connected
• Confusing parent node with visited node

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

bool dfs(int node, int parent, vector& graph, vector<bool>& visited) {
  visited[node] = true;
  for (int adj : graph[node]) {
    if (!visited[adj]) {
      if (dfs(adj, node, graph, visited)) return true;
    } else {
      return true;
    }
  }
  return false;
}

medium

A. It returns true even if adjacent node is the parent, causing false cycle detection.

B. It does not mark nodes as visited.

C. It uses wrong data types for graph and visited.

D. It never returns false.

Solution

1. Step 1: Review cycle detection condition

   The else block returns true if adjacent node is visited, but does not check if it is the parent.

2. Step 2: Identify impact of missing parent check

   Returning true for parent node causes false positive cycle detection.

3. Final Answer:

   It returns true even if adjacent node is the parent, causing false cycle detection. -> Option A

4. Quick Check:

   Check parent node before returning true for visited adjacency [OK]

Hint: Always exclude parent node when checking visited adjacency [OK]

Common Mistakes:

• Not checking if visited node is parent
• Returning true too early
• Incorrect recursion parameters

5. Given a graph with 5 nodes and edges: 0-1, 1-2, 2-3, 3-4, 4-1, which modification to the DFS cycle detection algorithm will correctly identify the cycle and also return the nodes involved in the cycle?

hard

A. Remove the parent check and mark all visited nodes as cycle nodes.

B. Use BFS instead of DFS to detect cycles and print nodes.

C. Modify DFS to store the path stack and return the cycle path when a back edge is found.

D. Count edges and nodes; if edges >= nodes, print all nodes as cycle.

Solution

1. Step 1: Understand cycle detection with node tracking

   DFS can track the current path using a stack or vector to record nodes visited in the current recursion.

2. Step 2: Modify DFS to return cycle path

   When a back edge is found (visited node not parent), extract nodes from the path stack to get cycle nodes.

3. Final Answer:

   Modify DFS to store the path stack and return the cycle path when a back edge is found. -> Option C

4. Quick Check:

   Track path in DFS to identify cycle nodes [OK]

Hint: Use path stack in DFS to retrieve cycle nodes [OK]

Common Mistakes:

• Using BFS which doesn't track path easily
• Ignoring parent check causing false cycles
• Using edge count alone to identify cycle nodes