Problem Statement

Given an undirected graph with V vertices labeled from 0 to V-1, and represented using an adjacency list where adj[i] lists all the nodes connected to vertex i, determine if the graph contains any cycles.

Problem Breakdown:

• The graph is undirected.
• The adjacency list adj represents the connections between vertices.
• We need to detect if the graph contains a cycle.

Examples

Example 1:

Input: V = 5
       adj = [
              [1],        // Node 0 is connected to 1
              [0, 2, 3],  // Node 1 is connected to 0, 2, and 3
              [1],        // Node 2 is connected to 1
              [1, 4],     // Node 3 is connected to 1 and 4
              [3]         // Node 4 is connected to 3
             ]
Output: False

Explanation:
        +-----+
        |  0  |
        +-----+
           |
           |
           |
        +-----+     +-----+
        |  1  |-----|  2  |
        +-----+     +-----+
          |
          |
          |
       +-----+      +-----+
       |  3  |------|  4  |
       +-----+      +-----+
The graph does not contain any cycles.

Example 2:

Input: V = 3
       adj = [
              [1],        // Node 0 is connected to 1
              [0, 2],     // Node 1 is connected to 0 and 2
              [1, 0],     // Node 2 is connected to 1 and 0
             ]
Output: True

Explanation:
        +-----+        +-----+
        |  0  |--------|  1  |
        +-----+        +-----+
            \           /
             \         /
              \       /
               \     /
               +-----+
               |  2  |
               +-----+
The graph does contain any cycles.

Different Approaches

1️⃣ BFS (Breadth-First Search)

In BFS, we use a queue to explore the graph level by level. For each node, we check if any of its neighbors have already been visited and are not the parent node. If this condition is met, a cycle exists.

Steps:

1. Use BFS starting from each unvisited node.
2. Track visited nodes and maintain a parent for each node (since BFS is not recursive).
3. For each neighbor of a node, if the neighbor is visited and is not the parent, then a cycle is detected.

Code:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool bfs(int start, vector<vector<int>>& adj, vector<bool>& visited) {
    queue<pair<int, int>> q;  // Queue to store the node and its parent
    visited[start] = true;
    q.push({start, -1});  // Push the starting node with no parent (-1)

    while (!q.empty()) {
        int node = q.front().first;
        int parent = q.front().second;
        q.pop();

        // Visit all neighbors of the current node
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push({neighbor, node});  // Push neighbor with the current node as its parent
            }
            // If the neighbor is visited and is not the parent, a cycle is detected
            else if (neighbor != parent) {
                return true;
            }
        }
    }
    return false;
}

bool containsCycleBFS(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);

    // Check all components of the graph (there could be multiple components)
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {  // If the node is not visited
            if (bfs(i, adj, visited)) {  // Perform BFS from this node
                return true;  // Cycle detected
            }
        }
    }

    return false;  // No cycle found in any component
}

int main() {
    int V = 5;
    vector<vector<int>> adj = {
        {1},        // Node 0 is connected to 1
        {0, 2, 3},  // Node 1 is connected to 0, 2, 3
        {1},        // Node 2 is connected to 1
        {1, 4},     // Node 3 is connected to 1, 4
        {3}         // Node 4 is connected to 3
    };

    if (containsCycleBFS(V, adj)) {
        cout << "The graph contains a cycle." << endl;
    } else {
        cout << "The graph does not contain a cycle." << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(V + E) (where V is the number of nodes and E is the number of edges in the graph)
  • Traversing the complete graph overall which taken O(V+E) time.
• Space Complexity: O(V)
  • Visited array takes O(V) space and in the worst case queue will store all nodes taking O(V) space.

2️⃣ DFS (Depth-First Search)

In an undirected graph, a cycle exists if during a DFS traversal, we visit an already visited vertex that is not the parent of the current vertex.

Steps:

1. Use DFS to explore each unvisited node.
2. Track visited nodes to avoid reprocessing.
3. For each neighbor of the current node, if the neighbor has already been visited and it is not the parent of the current node, a cycle exists.

Dry Run:

Code:

#include <iostream>
#include <vector>

using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;  // Mark the current node as visited
    
    // Traverse all the neighbors of the current node
    for (int neighbor : adj[node]) {
        // If the neighbor has not been visited, perform DFS on it
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited)) {
                return true;  // Cycle found
            }
        }
        // If the neighbor is visited and it's not the parent, we found a cycle
        else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool containsCycleDFS(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);  // To track visited nodes

    // Check all components of the graph
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {  // If the node is not visited
            if (dfs(i, -1, adj, visited)) {  // Perform DFS from this node
                return true;  // Cycle detected
            }
        }
    }
    
    return false;  // No cycle found in any component
}

int main() {
    int V = 5;
    vector<vector<int>> adj = {
        {1},        // Node 0 is connected to 1
        {0, 2, 3},  // Node 1 is connected to 0, 2, 3
        {1},        // Node 2 is connected to 1
        {1, 4},     // Node 3 is connected to 1, 4
        {3}         // Node 4 is connected to 3
    };

    if (containsCycleDFS(V, adj)) {
        cout << "The graph contains a cycle." << endl;
    } else {
        cout << "The graph does not contain a cycle." << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(V + E) (where V is the number of nodes and E is the number of edges in the graph)
  • Traversing the complete graph overall which taken O(V+E) time.
• Space Complexity: O(V)
  • Visited array takes O(V) space and in the worst case recursion stack will store O(V) calls taking O(V) space.