Cycle Detection in Undirected Graph (BFS)
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: How can cycle detection be performed in an undirected graph using BFS?, Graph, Undirected Graph, Adjacency List, Graph Traversal, Breadth-First Search, Depth-First Search, Queue, Recursion, Time Complexity, Space Complexity, tree properties, visited tracking, graph traversal, graph properties, cycle detection, bfs, Graph Types, Graph Traversal Utilities.
Problem: Cycle Detection in an Undirected Graph Problem Statement Given an undirected graph with N vertices and M edges, determine if it contains any cycle. An undirected graph contains a cycle if there is a path that starts and ends at the same vertex, visiting other vertices in between, and no edge is repeated. Input Specification The first line of input contains two integers N and M (1 ≤ N, M ≤ 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), representing an edge between vertex u and vertex v. Output Specification Print "Yes" if the graph contains a cycle, and "No" otherwise. Constraints 1 ≤ N, M ≤ 10^5 1 ≤ u, v ≤ N The graph may be disconnected. There are no self loops (an edge from a vertex to itself) or multiple edges between the same pair of vertices. Difficulty Level Medium