Cycle Detection in Undirected Graph Problem Statement
You are provided with an undirected graph containing 'N' vertices and 'M' edges. The vertices are numbered from 1 to 'N'. Your objective is to determine whether the graph contains a cycle.
A cycle is defined as a path that starts and ends at the same vertex, traversing each edge exactly once.
Example:
Input: N = 3, Edges = [[1, 2], [2, 3], [1, 3]].
Output: Yes
Explanation: There are 3 vertices in this graph and edges between vertex pairs (1, 2), (2, 3), and (1, 3). A cycle exists involving all these vertices.
Input:
The first line of input contains an integer 'T' representing the number of test cases. For each test case: The first line contains two space-separated integers 'N' and 'M', denoting the number of vertices and edges. The next 'M' lines each contain two space-separated integers representing an edge between two vertices in the graph.
Output:
For each test case, print "Yes" if a cycle is present in the graph; otherwise, print "No".
Constraints:
- 1 <= T <= 10
- 1 <= N <= 5000
- 0 <= M <= min(5000, (N * (N - 1)) / 2)
- 1 <= edges[i][0] <= N
- 1 <= edges[i][1] <= N
- Time Limit: 1 sec
Note:
Please note that: 1. There are no parallel edges between two vertices. 2. There are no self-loops, i.e., an edge that connects a vertex to itself. 3. The graph can be disconnected.
AnswerBot
2d
Detect cycles in an undirected graph with given vertices and edges.
Use Depth First Search (DFS) to traverse the graph and detect cycles.
Maintain a visited array to keep track of visited vertices and a...read more
Help your peers!
Add answer anonymously...
Top PayPal Software Engineer interview questions & answers
Popular interview questions of Software Engineer
Top HR questions asked in PayPal Software Engineer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app