Prerequisites: Graphs, DFS
Problem: Implement the algorithm to check if a given undirected graph contains any cycle.
Solution Approach: As mentioned on the problem statement page, we use depth-first search (DFS) and track the parent of each node during the traversal. While exploring the neighbors of a node, if a neighbor is encountered that has been already visited but is not the parent of the current node, then there is a back edge, indicating the presence of a cycle in the graph. The algorithm iterates through all vertices, performing DFS from each unvisited vertex, and detects cycles if any during the process.
Time complexity: O(N + M) as we need to explore all nodes using DFS.
Space complexity: O(N) as we need to store the visited states of the nodes in an array.