Cycle Detection in Directed Graph (BFS)
Topological Sort DSA practice problem on Onlearn.
Difficulty: hard.
Topics: How can cycles be detected in a directed graph using BFS?, Graph, Directed Graph, Adjacency List, Breadth-First Search, Queue, Graph Traversal, Topological Sorting, Time Complexity, Space Complexity, topological sort, kahn's algorithm, graph traversal, graph properties, cycle detection, bfs, Topological Sort (Kahn's Algorithm).
Problem Statement You are given a directed graph with N vertices and M edges. Your task is to determine if the given graph contains any cycle. A cycle in a directed graph is a path that starts and ends at the same vertex, where all intermediate vertices are distinct. Input Specification The first line contains two integers, N and M (1 \le N \le 10^5, 0 \le M \le 2 \times 10^5), representing the number of vertices and the number of edges, respectively. The next M lines each contain two integers, u and v (1 \le u, v \le N), representing a directed edge from vertex u to 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 contains a cycle: 2 3 4 2. Sample Input 2: Sample Output 2: Explanation 2: The graph is a Directed Acyclic Graph (DAG).