Detect a cycle in an undirected graph

Intuition:

In an undirected graph, a cycle is formed when a path exists that returns to the starting vertex without reusing an edge. The key idea is that during traversal (e.g., using Breadth-First Search (BFS) for this approach), if we encounter a vertex that has already been visited and is not the immediate parent of the current vertex, a cycle exists.

Approach:

A helper function performs BFS to detect cycles, using a queue to track nodes and their parents. For each unvisited node, initialize the queue with the node and mark it as visited.
While the queue is not empty, process each node's neighbors:
- If a neighbor is unvisited, mark it visited and enqueue it.
- If a neighbor is visited and not the parent, a cycle is detected.
Return true if any cycle is found during traversal.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    // Function to perform BFS traversal
    bool bfs(int i, vector<int> adj[], 
            vector<bool> &visited) {
        
        // Queue to store {node, parent}
        queue<pair<int, int>> q;
        
        /* Push initial node in queue 
        with no one as parent */
        q.push({i, -1});
        
        // Mark the node as visited
        visited[i] = true;
        
        // Until the queue is empty
        while(!q.empty()) {
            
            // Get the node and its parent
            int node = q.front().first;
            int parent = q.front().second;
            q.pop();
            
            // Traverse all the neighbors
            for(auto it : adj[node]) {
                
                // If not visited
                if(!visited[it]) {
                    
                    // Mark the node as visited
                    visited[it] = true;
                    
                    /* Push the new node in queue 
                    with curr node as parent */
                    q.push({it, node});
                } 
                
                /* Else if it is visited with some 
                different parent a cycle is detected */
                else if(it != parent) return true;
            }
        }
        return false;
    }

public:
    // Function to detect cycle in an undirected graph.
    bool isCycle(int V, vector<int> adj[]) {
        
        // Visited array
        vector<bool> visited(V, false);
        
        /* Variable to store if 
        there is a cycle detected */
        bool ans = false;
        
        // Start Traversal from every unvisited node
        for(int i=0; i<V; i++) {
            if(!visited[i]) {
                
                // Start BFS traversal and update result
                ans = bfs(i, adj, visited);
                
                // Break if a cycle is detected
                if(ans) break;
            }
        }
        return ans;
    }
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
        {1, 3}, 
        {0, 2, 4}, 
        {1, 5}, 
        {0, 4}, 
        {1, 3, 5}, 
        {2, 4}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to detect 
    cycle in given graph. */
    bool ans = sol.isCycle(V, adj);
    
    // Output
    if(ans) 
        cout << "The given graph contains a cycle.";
    else 
        cout << "The given graph does not contain a cycle.";
    
    return 0;
}
import java.util.*;

class Solution {
    
    // Function to perform BFS traversal
    private boolean bfs(int i, 
        List<Integer> adj[], 
        boolean[] visited) {
            
        // Queue to store {node, parent}
        Queue<int[]> q = new LinkedList<>();
        
        /* Push initial node in queue 
        with no one as parent */
        q.add(new int[]{i, -1});
        
        // Mark the node as visited
        visited[i] = true;
        
        // Until the queue is empty
        while (!q.isEmpty()) {
            
            // Get the node and its parent
            int[] current = q.poll();
            int node = current[0];
            int parent = current[1];
            
            // Traverse all the neighbors
            for (int it : adj[node]) {
                
                // If not visited
                if (!visited[it]) {
                    // Mark the node as visited
                    visited[it] = true;
                    
                    /* Push the new node in queue 
                    with curr node as parent */
                    q.add(new int[]{it, node});
                } 
                
                /* Else if it is visited with some 
                different parent a cycle is detected */
                else if (it != parent) return true;
            }
        }
        return false;
    }

    /* Function to detect cycle 
    in an undirected graph. */
    public boolean isCycle(int V, 
            List<Integer> adj[]) {
                
        // Visited array 
        boolean[] visited = new boolean[V];
        
        /* Variable to store if 
        there is a cycle detected */
        boolean ans = false;
        
        // Start Traversal from every unvisited node
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                
                // Start BFS traversal and update result
                ans = bfs(i, adj, visited);
                
                // Break if a cycle is detected
                if (ans) break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int V = 6;
        List<Integer> adj[] = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[0].addAll(Arrays.asList(1, 3));
        adj[1].addAll(Arrays.asList(0, 2, 4));
        adj[2].addAll(Arrays.asList(1, 5));
        adj[3].addAll(Arrays.asList(0, 4));
        adj[4].addAll(Arrays.asList(1, 3, 5));
        adj[5].addAll(Arrays.asList(2, 4));
        
        // Creating an instance of Solution class
        Solution sol = new Solution();
        
        // Function call to detect cycle in given graph.
        boolean ans = sol.isCycle(V, adj);
        
        // Output
        if (ans)
            System.out.println("The given graph contains a cycle.");
        else
            System.out.println("The given graph does not contain a cycle.");
    }
}
from collections import deque

class Solution:
    
    # Function to perform BFS traversal
    def bfs(self, i, adj, visited):
        # Queue to store (node, parent)
        q = deque()
        
        # Push initial node in queue 
        # with no one as parent
        q.append((i, -1))
        
        # Mark the node as visited
        visited[i] = True
        
        # Until the queue is empty
        while q:
            # Get the node and its parent
            node, parent = q.popleft()
            
            # Traverse all the neighbors
            for it in adj[node]:
                # If not visited
                if not visited[it]:
                    # Mark the node as visited
                    visited[it] = True
                    
                    # Push the new node in queue 
                    # with curr node as parent
                    q.append((it, node))
                    
                # Else if it is visited with some 
                # different parent a cycle is detected
                elif it != parent:
                    return True
        return False

    # Function to detect cycle in an undirected graph.
    def isCycle(self, V, adj):
        visited = [False] * V
        ans = False
        
        # Start Traversal from every unvisited node
        for i in range(V):
            if not visited[i]:
                # Start BFS traversal and update result
                ans = self.bfs(i, adj, visited)
                
                # Break if a cycle is detected
                if ans:
                    break
        return ans

if __name__ == "__main__":
    V = 6
    adj = [
        [1, 3],
        [0, 2, 4],
        [1, 5],
        [0, 4],
        [1, 3, 5],
        [2, 4]
    ]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to detect cycle in given graph.
    ans = sol.isCycle(V, adj)
    
    # Output
    if ans:
        print("The given graph contains a cycle.")
    else:
        print("The given graph does not contain a cycle.")
class Solution {

    // Function to perform BFS traversal
    bfs(i, adj, visited) {
        // Queue to store {node, parent}
        let q = [];
        
        // Push initial node in queue with no one as parent
        q.push([i, -1]);
        
        // Mark the node as visited
        visited[i] = true;
        
        // Until the queue is empty
        while (q.length > 0) {
            // Get the node and its parent
            let [node, parent] = q.shift();
            
            // Traverse all the neighbors
            for (let it of adj[node]) {
                // If not visited
                if (!visited[it]) {
                    // Mark the node as visited
                    visited[it] = true;
                    
                    /* Push the new node in queue 
                    with curr node as parent */
                    q.push([it, node]);
                } 
                /* Else if it is visited with some 
                different parent a cycle is detected */
                else if (it !== parent) {
                    return true;
                }
            }
        }
        return false;
    }

    // Function to detect cycle in an undirected graph.
    isCycle(V, adj) {
        let visited = new Array(V).fill(false);
        let ans = false;
        
        // Start Traversal from every unvisited node
        for (let i = 0; i < V; i++) {
            if (!visited[i]) {
                // Start BFS traversal and update result
                ans = this.bfs(i, adj, visited);
                
                // Break if a cycle is detected
                if (ans) break;
            }
        }
        return ans;
    }
}

const V = 6;
const adj = [
    [1, 3],
    [0, 2, 4],
    [1, 5],
    [0, 4],
    [1, 3, 5],
    [2, 4]
];

// Creating an instance of Solution class
const sol = new Solution();

// Function call to detect cycle in given graph.
const ans = sol.isCycle(V, adj);

// Output
if (ans) 
    console.log("The given graph contains a cycle.");
else 
    console.log("The given graph does not contain a cycle.");

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.

Intuition:

In an undirected graph, a cycle is formed when a path exists that returns to the starting vertex without reusing an edge. The key idea is that during traversal (e.g., using Depth-First Search (BFS) for this approach), if we encounter a vertex that has already been visited and is not the immediate parent of the current vertex, a cycle exists.

Approach:

A helper function performs DFS to detect cycles, keeping track of nodes and their parents. For each unvisited node, initialize the mark the node as visited.
Traverse the neighbors of the node:
- If a neighbor is unvisited, mark it visited and recursively perform DFS from it.
- If a neighbor is visited and not the parent, a cycle is detected.
Return true if any cycle is found during traversal.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    
    // Function to perform DFS traversal
    bool dfs(int i, vector<int> adj[], 
            vector<bool> &visited, 
            int prev) {
                
        // Mark the node as visited
        visited[i] = true;
        
        // Traverse all the neighbors
        for(auto node : adj[i]) {
            
            // If not visited
            if(!visited[node]) {
                
                /* Recursively perform DFS, and 
                return true if cycle is found */
                if(dfs(node, adj, visited, i)) {
                    return true;
                }
            }
            
            /* Else if it is visited with some 
            different parent a cycle is detected */
            else if(node != prev){
                return true;
            }
            
        }
        
        // Return false if no cycle is detected
        return false;
    }

public:
    // Function to detect cycle in an undirected graph.
    bool isCycle(int V, vector<int> adj[]) {
        
        // Visited array
        vector<bool> visited(V, false);
        
        // Start Traversal from every unvisited node
        for(int i=0; i<V; i++) {
            if(!visited[i]) {
                
                /* Start DFS traversal, and 
                return true if cycle is found */
                if(dfs(i, adj, visited, -1)) {
                    return true;
                }
            }
        }
        
        // Return false if no cycle is detected
        return false;
    }
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
        {1, 3}, 
        {0, 2, 4}, 
        {1, 5}, 
        {0, 4}, 
        {1, 3, 5}, 
        {2, 4}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to detect 
    cycle in given graph. */
    bool ans = sol.isCycle(V, adj);
    
    // Output
    if(ans) 
        cout << "The given graph contains a cycle.";
    else 
        cout << "The given graph does not contain a cycle.";
    
    return 0;
}
import java.util.*;

class Solution {
    
    // Function to perform DFS traversal
    private boolean dfs(int i, List<Integer> adj[], 
                        boolean[] visited, int prev) {
        // Mark the node as visited
        visited[i] = true;
        
        // Traverse all the neighbors
        for (int node : adj[i]) {
            
            // If not visited
            if (!visited[node]) {
                
                /* Recursively perform DFS, and 
                return true if cycle is found */
                if (dfs(node, adj, visited, i)) {
                    return true;
                }
            }
            
            /* Else if it is visited with some 
            different parent a cycle is detected */
            else if (node != prev) {
                return true;
            }
        }
        
        // Return false if no cycle is detected
        return false;
    }

    // Function to detect cycle in an undirected graph.
    public boolean isCycle(int V, List<Integer> adj[]) {
        
        // Visited array
        boolean[] visited = new boolean[V];
        
        // Start Traversal from every unvisited node
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                /* Start DFS traversal, and 
                return true if cycle is found */
                if (dfs(i, adj, visited, -1)) {
                    return true;
                }
            }
        }
        
        // Return false if no cycle is detected
        return false;
    }

    public static void main(String[] args) {
        int V = 6;
        List<Integer> adj[] = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[0].addAll(Arrays.asList(1, 3));
        adj[1].addAll(Arrays.asList(0, 2, 4));
        adj[2].addAll(Arrays.asList(1, 5));
        adj[3].addAll(Arrays.asList(0, 4));
        adj[4].addAll(Arrays.asList(1, 3, 5));
        adj[5].addAll(Arrays.asList(2, 4));
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to detect 
        cycle in given graph. */
        boolean ans = sol.isCycle(V, adj);
        
        // Output
        if (ans) 
            System.out.println("The given graph contains a cycle.");
        else 
            System.out.println("The given graph does not contain a cycle.");
    }
}
class Solution:
    
    # Function to perform DFS traversal
    def dfs(self, i, adj, visited, prev):
        # Mark the node as visited
        visited[i] = True
        
        # Traverse all the neighbors
        for node in adj[i]:
            
            # If not visited
            if not visited[node]:
                
                # Recursively perform DFS, and 
                # return true if cycle is found
                if self.dfs(node, adj, visited, i):
                    return True
                    
            # Else if it is visited with some 
            # different parent a cycle is detected
            elif node != prev:
                return True
        
        # Return false if no cycle is detected
        return False

    # Function to detect cycle in an undirected graph.
    def isCycle(self, V, adj):
        # Visited array
        visited = [False] * V
        
        # Start Traversal from every unvisited node
        for i in range(V):
            if not visited[i]:
                
                # Start DFS traversal, and 
                # return true if cycle is found
                if self.dfs(i, adj, visited, -1):
                    return True
        
        # Return false if no cycle is detected
        return False

if __name__ == "__main__":
    V = 6
    adj = [
        [1, 3], 
        [0, 2, 4], 
        [1, 5], 
        [0, 4], 
        [1, 3, 5], 
        [2, 4]
    ]
    
    ''' Creating an instance of 
    Solution class '''
    sol = Solution()
    
    ''' Function call to detect 
    cycle in given graph. '''
    ans = sol.isCycle(V, adj)
    
    # Output
    if ans: 
        print("The given graph contains a cycle.")
    else: 
        print("The given graph does not contain a cycle.")
class Solution {
    // Function to perform DFS traversal
    dfs(i, adj, visited, prev) {
        // Mark the node as visited
        visited[i] = true;
        
        // Traverse all the neighbors
        for (let node of adj[i]) {
            // If not visited
            if (!visited[node]) {
                /* Recursively perform DFS, and 
                return true if cycle is found */
                if (this.dfs(node, adj, visited, i)) {
                    return true;
                }
            }
            /* Else if it is visited with some 
            different parent a cycle is detected */
            else if (node !== prev) {
                return true;
            }
        }
        
        // Return false if no cycle is detected
        return false;
    }

    // Function to detect cycle in an undirected graph.
    isCycle(V, adj) {
        // Visited array
        let visited = new Array(V).fill(false);
        
        // Start Traversal from every unvisited node
        for (let i = 0; i < V; i++) {
            if (!visited[i]) {
                /* Start DFS traversal, and 
                return true if cycle is found */
                if (this.dfs(i, adj, visited, -1)) {
                    return true;
                }
            }
        }
        
        // Return false if no cycle is detected
        return false;
    }
}

const main = () => {
    const V = 6;
    const adj = [
        [1, 3], 
        [0, 2, 4], 
        [1, 5], 
        [0, 4], 
        [1, 3, 5], 
        [2, 4]
    ];
    
    /* Creating an instance of 
    Solution class */
    const sol = new Solution();
    
    /* Function call to detect 
    cycle in given graph. */
    const ans = sol.isCycle(V, adj);
    
    // Output
    if (ans) 
        console.log("The given graph contains a cycle.");
    else 
        console.log("The given graph does not contain a cycle.");
};

main();

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.

Problem List

Detect a cycle in an undirected graph

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code