Start practising

Undirected Graph Cycle

Medium Graphs Cycle Detection Original on GeeksforGeeks

Undirected Graph Cycle is a medium graphs problem solved with the cycle detection pattern. The best approach, union-find, runs in O(E · α(V)) time and O(V) space. Below are 2 approaches in Java, from bfs with parent tracking up.

Problem

Given an undirected graph with V vertices and a list of edges, decide whether it contains a cycle.

Examples

Example 1

Input
V = 4, edges = [[0,1],[1,2],[2,0],[2,3]]
Output
true
Why
0 → 1 → 2 → 0.

Example 2

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

Constraints

  • 1 <= V, E <= 10^5; the graph may be disconnected.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
BFS with parent trackingO(V + E)O(V)
Union-FindO(E · α(V))O(V)

1BFS with parent tracking

TimeO(V + E)
SpaceO(V)

BFS from every unvisited node, storing each node's parent. A visited neighbour that is not the parent closes a cycle.

  1. Queue (node, parent).
  2. For each neighbour: unvisited → enqueue; visited and != parent → cycle.
Java
class Solution {
    public boolean isCycle(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[V];
        for (int s = 0; s < V; s++) {
            if (seen[s]) continue;
            Queue<int[]> q = new ArrayDeque<>();
            q.add(new int[] { s, -1 });
            seen[s] = true;
            while (!q.isEmpty()) {
                int[] cur = q.poll();
                for (int v : adj.get(cur[0])) {
                    if (!seen[v]) { seen[v] = true; q.add(new int[] { v, cur[0] }); }
                    else if (v != cur[1]) return true;
                }
            }
        }
        return false;
    }
}

2Union-Find

TimeO(E · α(V))
SpaceO(V)

Process each edge. If its two endpoints are already in the same set, this edge closes a cycle. Otherwise union them.

  1. parent[i] = i.
  2. For each edge (u, v): if find(u) == find(v) return true; else union.
Java
class Solution {
    private int[] parent;

    public boolean isCycle(int V, int[][] edges) {
        parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) return true;
            parent[a] = b;
        }
        return false;
    }

    private int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
}

Edge cases to test

  • Disconnected components (start a search from every unvisited node)
  • The edge back to your parent is not a cycle

Hints

Hint 1

In DFS or BFS, reaching a visited node that is not your parent means there is a cycle.

FAQ

What is the best time complexity for Undirected Graph Cycle?

Union-Find runs in O(E · α(V)) time and O(V) extra space.

Which pattern does Undirected Graph Cycle use?

It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Directed Graph Cycle, Is Graph Bipartite?.

Is there a brute force solution for Undirected Graph Cycle?

Yes. BFS with parent tracking takes O(V + E) time and O(V) space. BFS from every unvisited node, storing each node's parent.

Which edge cases should I test for Undirected Graph Cycle?

Disconnected components (start a search from every unvisited node); The edge back to your parent is not a cycle.