Question

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

Answer 1

so to solve this kind of question we will use adjacency list because it uses less space and time complexity to traverse it is O(V+E) where V is vertex and E is the Edge

so the idea is to create an adjacency list and also create a bool array name it visited and initially mark all false.

the visited array will keep the record of which vertex is visited or not

and one variable parent which will tell us the parent of a vertex. in simple words from which vertex we are reaching to which, vertex like 0:{1,2} in this we can reach from 0->1 and 0->2 so parents of 1 and 2 are 0.

we will use dfs for solving this problem

To print the cycle what we can do is ->visited will give which vertex we have visited and if cycle present we will return true and we will iterate in visited array to see which vertex are true and that will be our answer

time complexity -O(V+E) where v is vertex and E is an edge

so the solution is below

if any doubt, comment below