Detect Cycle in an Undirected Graph

Standard Bar Graphs · Traversal Problems O(V + E) · O(V)

The Redundant Duct Audit

A plant's air-duct network is undirected, and the auditor must flag whether any duct forms a loop — a ring that lets air return to where it started without retracing. Walking the network from junction to junction, the only legitimate way to meet an already-logged junction is the one you just came from; meeting any other logged junction means a loop exists.

Input: An integer V and an adjacency list adj where adj[i] lists every junction directly connected to junction i.

Output: Return true if the undirected graph contains a cycle, otherwise false.

Constraints

1 <= V <= 10^5
0 <= number of edges <= 2 * 10^5
0 <= adj[i][j] < V

Examples

Example 1

Input: {"V":4,"adj":[[1,2],[0,2],[0,1],[3]]}
Output: true
0-1-2-0 closes a triangle; junction 3 is an innocent bystander.

Example 2

Input: {"V":4,"adj":[[1,2],[0,3],[0,3],[1,2]]}
Output: true
The square 0-1-3-2-0 is a four-way loop.

Solve this in your browser →

Also on LeetCode ↗