Does an Undirected Graph Have a Cycle?

MediumGraphsUnion findDfs203 tests

You are given an undirected graph with n vertices numbered 0 to n - 1, and a list edges. Each edge [u, v] joins vertex u and vertex v, and you can move along it in both directions.

A cycle is a path that starts at a vertex, moves along at least three different edges without using any edge twice, and comes back to the same vertex.

Return true if the graph has at least one cycle, and false if it has none.

Note

The graph may have several separate parts. Check every part.
No edge joins a vertex to itself, and no pair of vertices is joined by more than one edge.

Hint: add the edges one at a time and keep track of which vertices are already connected (for example with union-find). If an edge joins two vertices that are already connected, it closes a cycle.

Examples

Example 1

Input:: 6, [[0,1],[1,2],[3,4],[4,5],[5,3]]
Output:: true

Vertices 3, 4 and 5 form a cycle: 3 → 4 → 5 → 3. The part with 0, 1 and 2 has no cycle, but one cycle anywhere is enough.

Example 2

Input:: 5, [[0,1],[0,2],[2,3],[2,4]]
Output:: false

This graph is a tree. There is only one path between any two vertices, so no path can come back to its start.

Example 3

Input:: 3, []
Output:: false

With no edges there is no cycle.

Constraints

1 <= n <= 15
0 <= edges.length <= 30
edges[i] = [u, v] with 0 <= u, v < n and u != v
No pair of vertices appears in more than one edge.

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.