Detect cycle in an undirected graph

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

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.

Example 2:

Input: 
V = 4, E = 2
adj = {{}, {2}, {1, 3}, {2}}
Output: 0
Explanation: 

No cycle in the graph.

 

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 Space Complexity: O(V)

 

Constraints:
1 ≤ V, E ≤ 105

solution :

using dfs : 

class Solution {   public:     // Function to detect cycle in an undirected graph.     bool dfs(int i , vector<int>adj[] , vector<bool>&visited , int V , int p )     {         visited[i] = true;               for( int j : adj[i])         {                            if(!visited[j])             {                   if(dfs(j , adj , visited , V , i ) == true)                   return true;             }             else             if(  p != j)             {                                 return true;             }                     }         return false;     }     bool isCycle(int V, vector<int> adj[]) {                         int p = -1;         vector<bool>visited(V+1 , false);         for(int i =0 ; i < V ; i++)         {   if(!visited[i])           {             if(dfs( i ,adj , visited , V, p) == true)                 return true;           }         }         return false;     } };

using bfs : 

Class Solution{ bool detect(int src  ,  vector<int>&visited , vector<int>adj[])     {         visited[src] = 1;         queue<pair<int, int>>q;         q.push({src, -1});         while(!q.empty())         {             int node = q.front().first;             int parent = q.front().second;             q.pop();             for(int x : adj[node])             {                 if(visited[x] != 1)                 {                     q.push({x, node});                     visited[x] = 1;                 }                 else                 if(parent != x)                 {                     return true;                 }             }                     }         return false;     }   public:     // Function to detect cycle in an undirected graph.     bool isCycle(int V, vector<int> adj[]) {                 queue<pair<int , int>>q;         vector<int>visited(V, 0);         for(int i = 0 ; i < V ; i++)         {             if(!visited[i])             {                 if(detect(i , visited , adj))                 return true;             }         }         return false;     } };

References :  https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1