Undirected Graph Cycle | Practice Easy 0 attempts
GeeksforGeeks ↗

Undirected Graph Cycle | Practice

Easy GraphBFSDFS GeeksforGeeks

You're handed an undirected graph and need to figure out whether it has a cycle anywhere in it — a route that leaves a vertex, travels along distinct edges without reusing any of them, and eventually comes back to that same starting vertex.

The graph isn't guaranteed to be connected, so check every component. The input is V and an edge list edges; each undirected edge is listed exactly once.

Input Format
Implement hasCycle(V, edges). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
V = 5
edges = [[0,1],[1,2],[2,0],[3,4]]
Output
true

Example 2

Input
V = 3
edges = [[0,1],[1,2]]
Output
false
Constraints
  • 1 <= V <= 10^5
  • 0 <= edges.length <= 10^5
  • Each edge is a pair of vertex indices in [0,V-1].
Test Cases (2)
Case 1
Args: [5,[[0,1],[1,2],[2,0],[3,4]]] Expected: true
Case 2
Args: [3,[[0,1],[1,2]]] Expected: false
Topics
GraphBFSDFS

Union-Find

javascript
function hasCycle(V, edges) {
  const parent = Array.from({length:V},(_,i)=>i);
  const size = Array(parent.length).fill(1);
  function find(x) { while(parent[x]!==x){parent[x]=parent[parent[x]];x=parent[x];}return x; }
  function union(a,b) { a=find(a);b=find(b);if(a===b)return;if(size[a]<size[b])[a,b]=[b,a];parent[b]=a;size[a]+=size[b]; }
  for (const [u,v] of edges) {
    if (find(u)===find(v)) return true;
    union(u,v);
  }
  return false;
}

Time: O(E α(V)) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript