Input : V = 8, E = 7

Output : False
Explanation : No cycle is present in the given graph

Input : V = 8, E = 6

Output : True
Explanation : 4->5->6->4 is a cycle.

Disclaimer: Here is the practice link to help you assess your knowledge better. It's highly recommend trying to solve it before looking at the solution.

Approach

Algorithm

In an undirected graph, a cycle exists if while traversing the graph, we encounter a node that has already been visited and it is not the parent of the current node. Since undirected edges connect both ways, simply seeing a visited node does not guarantee a cycle (it could just be the parent). The trick is to check whether a visited neighbor is different from the parent, if so, we’ve found a cycle.

Depth First Search works well here by using a queue to explore the graph level by level. Along with each node, we also store its parent. When we find an adjacent node that has already been visited and is not the parent, that confirms a cycle.

Maintain a visited array to keep track of visited nodes.
Iterate through all nodes to handle disconnected components.
If a node is unvisited, start a DFS from it with the parent set to -1 (or null).
In DFS, for the current node, explore all its neighbors.
If a neighbor is not visited, recursively call DFS with the current node as parent.
If a neighbor is already visited and is not the parent, then a cycle exists.
If the DFS completes without such a condition, no cycle exists.