Last active
May 9, 2024 04:59
-
-
Save Ch-sriram/42d46bc987002d2e4cb13d8be1eedba7 to your computer and use it in GitHub Desktop.
Detect Cycle in an Undirected Graph [TC: O(V+E); SC: O(V)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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].
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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].