Detect cycle in an undirected graph (DSA)

 

Problem Statement:(👈click here for GFG)

Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not. Graph is in the form of adjacency list where adj[i] contains all the nodes ith node is having edge with.

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:

class Solution {
  // Function to detect cycle in an undirected graph.
  isCycle(V, adj) {
    // Create an array to keep track of visited vertices
    let visited = new Array(V).fill(false);

    // Perform DFS from each unvisited vertex
    for (let i = 0; i < V; i++) {
      if (!visited[i]) {
        if (dfs(i, -1, visited, adj)) {
          // If a cycle is detected, return true
          return 1;
        }
      }
    }

    // If no cycle is detected, return false
    return 0;
  }
}

// Helper function to perform DFS
function dfs(vertex, parent, visited, adj) {
  // Mark the current vertex as visited
  visited[vertex] = true;

  // Traverse all the adjacent vertices
  for (let i = 0; i < adj[vertex].length; i++) {
    let adjVertex = adj[vertex][i];

    // If the adjacent vertex is not visited, visit it and continue DFS
    if (!visited[adjVertex]) {
      if (dfs(adjVertex, vertex, visited, adj)) {
        return true;
      }
    }
    // If the adjacent vertex is visited and not the parent of the current vertex, a cycle is detected
    else if (adjVertex != parent) {
      return true;
    }
  }

  // If no cycle is detected, return false
  return false;
}