« back

Detect cycle in an undirected graph

Tags : dfs, bfs, graph, geeksforgeeks, cpp, medium

Problem Statement - link #

Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not.

Your Task: You don’t need to read or print anything. Your task is to complete the function isCycle() which takes V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the undirected graph contains any cycle or not, return 1 if a cycle is present else return 0.

NOTE: The adjacency list denotes the edges of the graph where edges[i] stores all other vertices to which ith vertex is connected.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:  
V = 5, E = 5
adj = [[1], [0, 2, 4], [1, 3], [2, 4], [1, 3]] 
Output: 1
Explanation: 
1->2->3->4->1 is a cycle.

Constraints #

Solutions #

class Solution
{
    public:
    // Function to detect cycle in an undirected graph.
    bool BFS(int i, int V, bool vis[], vector<int> adj[]){
        queue<pair<int, int>> q;
        q.push({i, -1});
        while(!q.empty()){
            int curr = q.front().first;
            int prev = q.front().second;
            vis[curr] = 1;
            q.pop();
            for(auto it : adj[curr]){
                if(!vis[it]){
                    vis[it] = 1;
                    q.push({it, curr});
                }else if(vis[it] == 1 && prev != it){
                    return true;
                }
            }
        }
        return false;
    }
    bool isCycle(int V, vector<int> adj[]) {
        // Code here
        bool vis[V]={0};
        for(int i = 0; i < V; i++){
            if(!vis[i]){
                if(BFS(i, V, vis, adj)){
                    return true;
                }
            }
        }
        return false;
    }
};