What is the brute force approach and complexity for Detect Cycle in an Undirected Graph?

Remove one edge; if its ends are still joined, it was on a cycle with time complexity O(E · (V + E)) and space complexity O(V + E).

What is the optimal approach and complexity for Detect Cycle in an Undirected Graph?

Union the edges in list order; the first edge whose ends already share a root closes a cycle with optimal time complexity O(E · α(V)) and space complexity O(V).

How do you identify the pattern for Detect Cycle in an Undirected Graph?

Look for key signals in the prompt: "undirected graph" indicates Edges have no arrows, so an edge only links two groups and direction does not matter.; "contains a cycle" indicates A cycle is an edge whose two ends are already linked, so find the first such edge.; "a list of E edges" indicates Each edge is read once, in list order, so one pass decides the answer..

Detect Cycle in an Undirected Graph

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelUnion-Find (cycle detection, undirected)

Complexity:O(E · (V + E))→O(E · α(V))

Key Insight

Read the edges in list order and keep the vertices in groups with Union-Find. If an edge joins two vertices that are already in one group, that edge closes a cycle, so return true. Every other edge just merges two groups.

Core Validity Invariant

Two vertices with the same root are already joined by a path of edges read so far, so an edge between them closes a cycle.

Problem

You get an undirected graph with V vertices, numbered 0 to V − 1, and a list of E edges. Each entry edges[i] = [u, v] is one edge joining vertices u and v. Each edge is listed once.

Return true if the graph contains a cycle, and false if it does not. The graph may have several separate pieces, and some of them may not touch vertex 0.

Input

V, the number of vertices, and edges, the list of edges.

Output

true if the graph has a cycle, otherwise false.

Example 1

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

Output: true

Vertices 0, 1 and 2 form a triangle: 0 → 1 → 2 → 0 comes back to the start.

Example 2

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

Output: false

The edges form one path, and a path has no cycle.

Constraints

• 1 ≤ V, E ≤ 10^5
• 0 ≤ edges[i][0], edges[i][1] < V

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A cycle means I can leave a vertex and come back to it without reusing an edge. How can I tell whether two vertices are already joined by a path?
2.
If I add the edges one at a time, when does a new edge create a cycle?
3.
Can an edge that joins two different pieces ever close a loop?
4.
If the graph has at least V edges, must it contain a cycle? What can I say about a graph with fewer edges?
5.
Do I need to search from every vertex, or can I decide while reading the list?

Brute force approach

Idea

Take one edge out of the list and search from one of its ends, using the other edges. If the search reaches the other end, the edge was on a cycle, because a second route between its ends exists. If the search misses it, the edge is a bridge that joins two pieces. Try every edge in turn.

Thinking process

1
Try the edges in list order, so each edge is tried exactly once.
2
Take the edges [0,1], [1,2], [2,0], [2,3] and remove [2,3]. From 2, the search reaches 0 and 1 but never 3. So [2,3] is a bridge, not part of a cycle.
3
Now remove [0,1]. From 0, the search goes 0 → 2 → 1 and reaches 1. So [0,1] lies on the triangle 0–1–2.
4
One edge on a cycle is enough: return true at once. If every edge is a bridge, the graph is a forest, so return false.

Visual

Green = reachable from the search start without the removed edge; orange = the edge removed this round; purple = the vertex being popped. Each edge costs one full search.

Brute force: remove each edge and searchV = 6, edges = [[0,1],[2,3],[1,2],[3,5],[3,4],[4,5]]step 1/17

graph (undirected)

edges

0–1

2–3

1–2

3–5

3–4

4–5

▲drop

State

edges to try: 6

Remove one edge; search from one end

Take one edge out of the list. If its two ends can still reach each other through the other edges, the edge was on a cycle. If not, it was a bridge: put it back and try the next edge. Orange = the edge removed for this round.

Code & Implementation

brute.cpp

class Solution {
public:
    bool isCycle(int V, vector<vector<int>>& edges) {
        int E = edges.size();

        // Remove one edge at a time. If its two ends are still joined by the other edges,
        // the removed edge was on a cycle.
        for (int drop = 0; drop < E; drop++) {
            int a = edges[drop][0], b = edges[drop][1];
            vector<vector<int>> g(V);
            for (int i = 0; i < E; i++) {
                if (i == drop) continue;
                g[edges[i][0]].push_back(edges[i][1]);
                g[edges[i][1]].push_back(edges[i][0]);
            }

            // Search from a and see whether b is reached.
            vector<bool> seen(V, false);
            queue<int> q;
            seen[a] = true;
            q.push(a);
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                for (int y : g[x])
                    if (!seen[y]) {
                        seen[y] = true;
                        q.push(y);
                    }
            }
            if (seen[b]) return true;
        }
        return false;
    }
};

import java.util.*;

class Solution {
    public boolean isCycle(int V, int[][] edges) {
        int E = edges.length;

        // Remove one edge at a time. If its two ends are still joined by the other edges,
        // the removed edge was on a cycle.
        for (int drop = 0; drop < E; drop++) {
            int a = edges[drop][0], b = edges[drop][1];
            List<List<Integer>> g = new ArrayList<>();
            for (int i = 0; i < V; i++) {
                g.add(new ArrayList<>());
            }
            for (int i = 0; i < E; i++) {
                if (i == drop) continue;
                g.get(edges[i][0]).add(edges[i][1]);
                g.get(edges[i][1]).add(edges[i][0]);
            }

            // Search from a and see whether b is reached.
            boolean[] seen = new boolean[V];
            Queue<Integer> q = new ArrayDeque<>();
            seen[a] = true;
            q.offer(a);
            while (!q.isEmpty()) {
                int x = q.poll();
                for (int y : g.get(x)) {
                    if (!seen[y]) {
                        seen[y] = true;
                        q.offer(y);
                    }
                }
            }
            if (seen[b]) return true;
        }
        return false;
    }
}

from typing import List
from collections import deque

class Solution:
    def isCycle(self, V: int, edges: List[List[int]]) -> bool:
        E = len(edges)

        # Remove one edge at a time. If its two ends are still joined by the other edges,
        # the removed edge was on a cycle.
        for drop in range(E):
            a, b = edges[drop][0], edges[drop][1]
            g: List[List[int]] = [[] for _ in range(V)]
            for i in range(E):
                if i == drop:
                    continue
                g[edges[i][0]].append(edges[i][1])
                g[edges[i][1]].append(edges[i][0])

            # Search from a and see whether b is reached.
            seen = [False] * V
            q = deque([a])
            seen[a] = True
            while q:
                x = q.popleft()
                for y in g[x]:
                    if not seen[y]:
                        seen[y] = True
                        q.append(y)
            if seen[b]:
                return True
        return False

export function isCycle(V: number, edges: number[][]): boolean {
    const E = edges.length;

    // Remove one edge at a time. If its two ends are still joined by the other edges,
    // the removed edge was on a cycle.
    for (let drop = 0; drop < E; drop++) {
        const a = edges[drop][0], b = edges[drop][1];
        const g: number[][] = Array.from({ length: V }, () => []);
        for (let i = 0; i < E; i++) {
            if (i === drop) continue;
            g[edges[i][0]].push(edges[i][1]);
            g[edges[i][1]].push(edges[i][0]);
        }

        // Search from a and see whether b is reached.
        const seen: boolean[] = new Array(V).fill(false);
        const q: number[] = [a];
        seen[a] = true;
        let head = 0;
        while (head < q.length) {
            const x = q[head++];
            for (const y of g[x]) {
                if (!seen[y]) {
                    seen[y] = true;
                    q.push(y);
                }
            }
        }
        if (seen[b]) return true;
    }
    return false;
}

Complexity

Time O(E · (V + E))Space O(V + E)

We try each of the E edges. Each try rebuilds the graph from the other edges and runs a search over V vertices and about 2E adjacency entries, so the total is E · (V + E). The rebuilt graph and the seen array take the space.

Optimized approach

Idea

Start from brute force

The brute force removes each edge and runs a fresh search. That search asks the same question again and again: are these two vertices still joined?

Find the repeated work

Each search walks almost the whole graph. Union-Find keeps the groups as the edges are read, so each "are these joined?" check costs almost O(1) instead of a search.

Define the state — what variables do I need?

parent[ ], sz[ ]: The disjoint-set forest over the vertices. A root (parent[v] = v) names its group, and sz is the group size, kept on roots.
edges[i] = [u, v]: The edge being read. The list is read once, from top to bottom.
root(u), root(v): The group names of the edge's two ends. Equal roots mean the ends are already joined.

Define validity

Two vertices with the same root are already joined by a path of edges read so far, so an edge between them closes a cycle.

Define the transitions — when does each pointer move, and why is it safe?

Before reading any edge

parent[v] = v and sz[v] = 1 for every vertex

No edges have been read yet, so every vertex stands alone in its own group.

Edge [u, v] with different roots

unite(u, v): hang the smaller root under the bigger one

The two ends were in different groups, so this edge cannot close a loop. Joining the groups keeps each group equal to the vertices linked so far.

Edge [u, v] with the same root

return true

The two ends were already linked by earlier edges, so this one adds a second route: a cycle.

All edges read with no repeat found

return false

Every edge joined two groups, so the edges form a forest, and a forest has no cycle.

What does the current window add to the answer?

Each edge is either a merge (no cycle yet) or the first edge that closes a cycle (the answer is true). No edge is read twice.

Code & Implementation

optimal.cpp

// Disjoint-set union with path compression and union by size.
struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) { iota(parent.begin(), parent.end(), 0); }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];   // path halving
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {               // false when a and b already share a root
        a = find(a), b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

class Solution {
public:
    bool isCycle(int V, vector<vector<int>>& edges) {
        DSU dsu(V);
        // Each edge is listed once, so read the list straight through.
        for (auto& e : edges)
            // Both ends already in one group: this edge closes a cycle.
            if (!dsu.unite(e[0], e[1])) return true;
        return false;
    }
};

import java.util.*;

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    int[] parent, sz;
    int groups;

    public DSU(int n) {
        parent = new int[n];
        sz = new int[n];
        groups = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    public int find(int x) {                              // the root that names x's group
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];         // path compression (halving): skip a level each step
            x = parent[x];
        }
        return x;
    }

    public boolean unite(int a, int b) {                     // false when a and b were already in one group
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) {
            int tmp = a; a = b; b = tmp;             // hang the smaller tree under the bigger one
        }
        parent[b] = a;
        sz[a] += sz[b];
        groups--;
        return true;
    }
}

class Solution {
    public boolean isCycle(int V, int[][] edges) {
        DSU dsu = new DSU(V);
        // Each edge is listed once, so read the list straight through.
        for (int[] e : edges) {
            // Both ends already in one group: this edge closes a cycle.
            if (!dsu.unite(e[0], e[1])) return true;
        }
        return false;
    }
}

from typing import List

# Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.groups = n

    def find(self, x: int) -> int:                              # the root that names x's group
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]         # path compression (halving): skip a level each step
            x = self.parent[x]
        return x

    def unite(self, a: int, b: int) -> bool:                     # false when a and b were already in one group
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a                                         # hang the smaller tree under the bigger one
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.groups -= 1
        return True

class Solution:
    def isCycle(self, V: int, edges: List[List[int]]) -> bool:
        dsu = DSU(V)
        # Each edge is listed once, so read the list straight through.
        for e in edges:
            # Both ends already in one group: this edge closes a cycle.
            if not dsu.unite(e[0], e[1]):
                return True
        return False

// Union-Find (Disjoint Set Union) with path compression + union by size.
class DSU {
    parent: number[];
    sz: number[];
    groups: number;

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.sz = new Array(n).fill(1);
        this.groups = n;
    }

    find(x: number): number {                              // the root that names x's group
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];  // path compression (halving): skip a level each step
            x = this.parent[x];
        }
        return x;
    }

    unite(a: number, b: number): boolean {                 // false when a and b were already in one group
        a = this.find(a);
        b = this.find(b);
        if (a === b) return false;
        if (this.sz[a] < this.sz[b]) {
            const tmp = a; a = b; b = tmp;                 // hang the smaller tree under the bigger one
        }
        this.parent[b] = a;
        this.sz[a] += this.sz[b];
        this.groups--;
        return true;
    }
}

export function isCycle(V: number, edges: number[][]): boolean {
    const dsu = new DSU(V);
    // Each edge is listed once, so read the list straight through.
    for (const e of edges) {
        // Both ends already in one group: this edge closes a cycle.
        if (!dsu.unite(e[0], e[1])) return true;
    }
    return false;
}

Complexity

Time O(E · α(V))Space O(V)

α is the inverse Ackermann function, below 5 for any input you will meet, so this is O(V + E) in practice. The DSU array takes O(V) space. A DFS with a parent check also solves this in O(V + E): if a visited neighbour is not the vertex you came from, there is a cycle. Union-Find is the pattern this section trains, and the same unite call powers the next three problems.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Remove one edge; if its ends are still joined, it was on a cycle	O(E · (V + E))	O(V + E)
Optimal	Union the edges in list order; the first edge whose ends already share a root closes a cycle	O(E · α(V))	O(V)

Why does this belong to this pattern?

Clues in the problem statement

“undirected graph”Edges have no arrows, so an edge only links two groups and direction does not matter.
“contains a cycle”A cycle is an edge whose two ends are already linked, so find the first such edge.
“a list of E edges”Each edge is read once, in list order, so one pass decides the answer.

Edges merge groups of vertices+an edge inside one group = a cycle+answer true at the first such edge→Union-Find (cycle detection, undirected)

The question is about groups, not about how far apart two vertices are, so Union-Find fits. The first edge whose two ends already share a root is a cycle. This is the basic cycle problem: Redundant Connection and Redundant Connection II use the same unite call. Direction changes the answer, though. In 0→1, 0→2, 1→2 there is no cycle, but Union-Find sees 1 and 2 already joined and reports one. Directed graphs need Topological Sort instead.

Don't make this mistake

Using the directed 'visited means cycle' rule

✗ bool dfs(int u) { seen[u] = true; for (int v : g[u]) { if (seen[v]) return true; // visited neighbour = cycle? if (dfs(v)) return true; } return false; }

✓ bool dfs(int u, int parent) { seen[u] = true; for (int v : g[u]) { if (v == parent) continue; // the edge we came in by is not a cycle if (seen[v]) return true; if (dfs(v, u)) return true; } return false; }

On the single edge [[0, 1]] with V = 2, dfs(0) visits 1, and then 1 sees 0 already visited, so the wrong code says true. But one edge is a tree. In an undirected graph the edge you came in by always looks visited, so you must skip the parent. The plain visited rule belongs to directed graphs.

Counting edges instead of joining groups

✗ return (int)edges.size() >= V; // E >= V: more edges than a tree allows

✓ if (!dsu.unite(e[0], e[1])) return true; // a cycle is a failed union

A forest on V vertices has at most V − 1 edges, so E ≥ V does prove a cycle. But E < V proves nothing when the graph has several pieces. Triangle 0–1–2 plus the lone vertices 3 and 4 has V = 5 and E = 3, and it still has a cycle, so the count wrongly says false.

Uniting before checking the roots

✗ dsu.unite(e[0], e[1]); if (dsu.find(e[0]) == dsu.find(e[1])) return true;

✓ if (!dsu.unite(e[0], e[1])) return true; // unite reports the failure itself

After a successful unite, the two ends always share a root, so the check fires on the very first edge. Even the single edge [[0, 1]], which has no cycle, returns true. Ask whether the ends are already joined before you merge them.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture