Cycle Detection in Undirected Graph (bfs)

Hard

A visited neighbour that is not your parent

Problem

Detect a cycle in an undirected graph using BFS (track parents).

In simple words

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

The idea

Run BFS carrying each vertex's parent. Meeting an already-visited vertex that is not the one you came from means two different paths reached it, which is a cycle.

The trick

Track the parent per queue entry, not globally.
The edge back to your parent is not a cycle.
Repeat from every unvisited vertex for disconnected graphs.

←→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.