190. Detect a cycle in an undirected graph
Given an undirected graph with V vertices labeled from 0 to V-1. The graph is represented using an adjacency list where adj[i] lists all nodes connected to node. Determine if the graph contains any cycles.
Note: The graph does not contain any self-edges (edges where a vertex is connected to itself).
Example 1:
Input: V = 6, adj= [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
Output: True
Explanation: The graph contains a cycle: 0 ->1 -> 2 -> 5 -> 4 -> 1.
Example 2:
Input: V = 4, adj= [[1, 2], [0], [0, 3], [2]]
Output: False
Explanation: The graph does not contain any cycles.
Now Your Turn!
Pick the correct output for the given inputInput: V = 4, adj= [[1, 2], [0, 2], [0, 1, 3], [2]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- E=number of edges
- 1 ≤ V, E ≤ 104