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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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?, Detect Cycles in 2D Grid.

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.