Detect Cycle in an Undirected Graph [TC: O(V+E); SC: O(V)]

cycle-undirected-dfs.cpp

// Problem Link: https://practice.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1/
// Solution Status: Accepted by GFG Judge

/**
* GYTWrkz Solutions Interview Question
* ------------------------------------
* Question 1: Given an Undirected Graph, find whether the Graph has a Cycle or Not (Discussed the approach with the interviewer).
*/

#include <iostream>
#include <vector>
using namespace std;

bool DFSRec(vector<int> *G, vector<bool> &visited, int s, int parent) {
  visited[s] = true; // mark the current vertex (which is 's') as visited
  for(int v: G[s]) // for each adjacent vertex 'v' of the current vertex 's'
    if(!visited[v]) { // if 'v' is not visited
      if(DFSRec(G, visited, v, s)) return true; // call DFS Recursively on 'v', passing the parent as 's', because v's parent is 's' (or, we came through 's', to get to 'v')
    }
  else if(v != parent) return true; // if 'v' is visited, but if it is not the parent vertex, then in that case, this is a back-edge, and so, there's a cycle.
  return false; // Base case: if there's no cycle after traversing through all the edges in the adj.list, we'll return false -> indicating that there's not cycle in the given graph G.
}

/* This function is used to detect a cycle in undirected graph
*  G[]: array of vectors to represent graph
*  V: number of vertices
*/
bool isCyclic(vector<int> G[], int V) {
  vector<bool> visited(V, false); // initiate the visited[] vector to all `false` values
  for(int i = 0; i < V; ++i) // loop to handle different components of the Graph - G[], in case the G is disconnected
    if(!visited[i]) // if the vertex is not visited
      if(DFSRec(G, visited, i, -1)) // Apply DFS Recursively by initiating the parent as -1. Even when we find another vertex of some other connected component, do the same.
        return true; // if there's a cycle, return true
  return false; // if we haven't found any cycle after traversing through all the vertices, return false
}

// For GFG Judge, this function not needed
void addEdge(vector<int> *G, int u, int v) {
  // Since Undirected, we add an edge from u->v & v->u
  G[u].push_back(v);
  G[v].push_back(u);
}

// For GFG Judge, this function not needed
int main() {
  int t;  cin >> t; // Test cases
  while(t--) {
    int V, E, u, v;   cin >> V >> E; // V => #Vertices, E => #Edges
    vector<int> G[V]; // Graph: G[], with 'V' Vertices (NOTE: For vertices from 1 to V, create a graph of vertices V+1 => vector<int> G[V+1];
    for(int i = 0; i < E; ++i) { // Adding the Edges to the Graph - G
      cin >> u >> v;
      addEdge(G, u, v);
    }
    cout << (isCyclic(G, V) ? "not-cyclic" : "cyclic") << "\n";
  }
  return 0;
}

Code provided seems to give runtime error especially for problem start vertex from to be considered from 1 to V. To fix small changes need to be done on line 49, vector G size should be declared as [V+1].

Code provided seems to give runtime error especially for problem start vertex from to be considered from 1 to V. To fix small changes need to be done on line 49, vector G size should be declared as [V+1].

Makes sense. I can added a comment and mentioned that the graph needs to have V+1 vertices if vertices go from 1 to V.

Thanks for pointing this out @Mohdsafwan7.