Cycle Detection in Undirected Graph (DFS)
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Cycle detection in undirected graphs using DFS, Graph, Undirected Graph, Adjacency List, Graph Traversal, Depth-First Search, Recursion, Time Complexity, Space Complexity, Algorithm, Connected Components, visited tracking, dfs, graph traversal, general programming, cycle detection, Graph Traversal Utilities.
Cycle Detection in Undirected Graph Problem Statement Given an undirected graph with N vertices and M edges, determine if it contains a cycle. A cycle is a path of distinct vertices and edges that starts and ends at the same vertex. Input Specification The first line contains two integers N and M (1 ≤ N ≤ 10^5, 0 ≤ M ≤ 2 10^5), representing the number of vertices and edges, respectively. The next M lines each contain two integers u and v (1 ≤ u, v ≤ N, u ≠ v), representing an undirected edge between vertex u and vertex v. Output Specification Print "Yes" if the graph contains at least one cycle, and "No" otherwise. Sample Test Cases Sample Input 1: Sample Output 1: Explanation 1: The graph has a cycle 1 2 3 1. Sample Input 2: Sample Output 2: Explanation 2: The graph is a simple path 1 2 3, which does not contain a cycle. Sample Input 3: Sample Output 3: Explanation 3: Two disconnected components, neither containing a cycle.