Detect a cycle in an undirected graph

Hard

Same rule, DFS or union-find

Problem

Return whether an undirected graph contains a cycle (DFS/BFS or union-find).

In simple words

Union-find: if an edge joins two nodes already in the same group, it closes a loop.

The idea

With DFS, a visited neighbour other than the parent proves a cycle. With union-find, an edge whose two endpoints already share a root closes a loop — both are O(V + E) in practice.

The trick

Ignore the parent edge, or every edge looks like a cycle.
Union-find is the cleaner choice when edges arrive one at a time.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 4, edges = [[0,1],[1,2],[2,3],[3,1]]
Output:: true
Explanation:: 3-1-2-3 forms a loop.

Example 2

Input:: n = 3, edges = [[0,1],[1,2]]
Output:: false
Explanation:: A simple chain → no cycle.

Example 3

Input:: n = 2, edges = [[0,1],[0,1]]
Output:: true
Explanation:: A repeated edge is a cycle.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.