☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Detect a cycle in an undirected graph

Hard TUF ID 501 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with V vertices numbered 0 to V - 1, as an adjacency list adj where adj.get(u) lists the neighbours of u. Every edge u - v therefore appears twice: v is in adj.get(u) and u is in adj.get(v). Return true if the graph contains a cycle, otherwise false.

A cycle is a walk that starts and ends at the same vertex, uses at least one edge, and never reuses an edge. The graph may be disconnected, and the cycle can sit in any component. As in the GfG version, the graph is simple: no self-loops and no two edges between the same pair of vertices.

Constraints: 1 ≤ V, E ≤ 10^5.

Example 1

V = 5, edges = 0-1, 1-2, 1-4, 2-3, 3-4
answer = true          // 1 - 2 - 3 - 4 - 1

Example 2

V = 4, edges = 0-1, 1-2, 2-3
answer = false         // a simple path, which is a tree

Example 3

V = 7, edges = 0-1, 1-2, 3-4, 4-5, 5-3
answer = true          // the cycle 3-4-5 lives in the second component; vertex 6 is isolated

A useful fact to keep in mind: a connected undirected graph is acyclic exactly when it is a tree, and every tree on k vertices has k - 1 edges. A cycle is an “extra” edge, one that connects two vertices that were already connected some other way. All four approaches below are different ways of catching that extra edge.

Approach 1: Brute force, remove each edge and test connectivity

Intuition. An edge u - v lies on a cycle exactly when u can still reach v after that edge is deleted, because the rest of the cycle is a second route between them. So test every edge separately: pretend it is gone, search from u, and see whether v turns up.

Algorithm.

  1. For every edge u - v (only when u < v, so each undirected edge is tested once):
  2. Run a DFS from u that is not allowed to use the direct step u -> v.
  3. If that search reaches v, return true.
  4. If no edge passes the test, return false.
static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) {
            if (u < v && reachableWithoutEdge(adj, u, v)) return true;   // u < v: test each edge once
        }
    }
    return false;
}

static boolean reachableWithoutEdge(List<List<Integer>> adj, int src, int dst) {
    boolean[] vis = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(src);
    vis[src] = true;
    while (!stack.isEmpty()) {
        int x = stack.pop();
        for (int y : adj.get(x)) {
            if (x == src && y == dst) continue;      // the edge under test is not allowed
            if (y == dst) return true;
            if (!vis[y]) { vis[y] = true; stack.push(y); }
        }
    }
    return false;
}

Complexity. Time O(E · (V + E)): one full graph search per edge. Space O(V) for the visited array and the stack.

It is correct, but with 10^5 edges it would do around 10^10 steps. The waste is obvious: every search rediscovers the same components from scratch.

Approach 2: Optimal, DFS that remembers the parent

Intuition. Do a single DFS and watch what each edge leads to. When we stand at node and look at a neighbour nb, there are three cases.

Why is the third case always a real cycle? The vertices visited so far, together with the tree edges, form a tree. Adding any non-tree edge between two of its vertices creates exactly one cycle. The only non-tree “edge” we must not count is the tree edge back to the parent, which is exactly what the parent check filters out.

Because the graph can have several components, the outer loop starts a fresh DFS from every vertex that is still unvisited.

Algorithm.

  1. Mark all vertices unvisited.
  2. For each unvisited vertex s, call dfsFrom(s, -1); return true if it reports a cycle.
  3. dfsFrom(node, parent): mark node; for each neighbour nb, recurse if unvisited, otherwise return true when nb != parent.
static boolean dfs(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    for (int s = 0; s < V; s++) {
        if (!vis[s] && dfsFrom(s, -1, adj, vis)) return true;   // one call per component
    }
    return false;
}

static boolean dfsFrom(int node, int parent, List<List<Integer>> adj, boolean[] vis) {
    vis[node] = true;
    for (int nb : adj.get(node)) {
        if (!vis[nb]) {
            if (dfsFrom(nb, node, adj, vis)) return true;
        } else if (nb != parent) {
            return true;                             // reached an already visited node by a second route
        }
    }
    return false;
}

Dry run on Example 1, with adj[1] = [0, 2, 4], adj[2] = [1, 3], adj[3] = [2, 4], adj[4] = [1, 3]:

call neighbour state action
dfsFrom(0, -1) 1 unvisited recurse
dfsFrom(1, 0) 0 parent skip
dfsFrom(1, 0) 2 unvisited recurse
dfsFrom(2, 1) 1 parent skip
dfsFrom(2, 1) 3 unvisited recurse
dfsFrom(3, 2) 4 unvisited recurse
dfsFrom(4, 3) 1 visited, parent is 3 cycle, return true

The edge 4 - 1 is the extra edge: 1 was already reached through 1 -> 2 -> 3 -> 4.

Complexity. Time O(V + E): each vertex is visited once and each adjacency list is scanned once. Space O(V) for vis plus the recursion stack, which can be V deep on a long path.

Approach 3: The same check with BFS

Intuition. Nothing in the argument above depends on the order of exploration; it only needs a spanning tree and the knowledge of which tree edge brought us to each vertex. BFS gives both if the queue stores {node, parent} pairs. A visited neighbour that is not the parent again means a second route. This version is preferable in Java when the graph can contain very long paths, because it uses a heap-allocated queue instead of the call stack. The BFS form is treated in detail in Cycle Detection in Undirected Graph (bfs).

static boolean bfs(int V, List<List<Integer>> adj) {
    boolean[] vis = new boolean[V];
    for (int s = 0; s < V; s++) {
        if (vis[s]) continue;
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{s, -1});
        vis[s] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int node = cur[0], parent = cur[1];
            for (int nb : adj.get(node)) {
                if (!vis[nb]) {
                    vis[nb] = true;
                    q.offer(new int[]{nb, node});
                } else if (nb != parent) {
                    return true;
                }
            }
        }
    }
    return false;
}

Complexity. Time O(V + E), space O(V) for the queue and the visited array.

Approach 4: Union-Find

Intuition. Build the graph one edge at a time and keep track of which vertices are already connected. A disjoint-set structure answers “are u and v already in the same component?” almost in constant time. If an edge arrives whose endpoints are already connected, that edge is precisely the extra edge that closes a cycle. Otherwise merge the two components. Each edge must be processed once, so the loop skips the copy where u > v.

static boolean unionFind(int V, List<List<Integer>> adj) {
    int[] root = new int[V];
    for (int i = 0; i < V; i++) root[i] = i;
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) {
            if (u > v) continue;                     // each undirected edge once
            int ru = find(root, u), rv = find(root, v);
            if (ru == rv) return true;               // u and v were already connected
            root[ru] = rv;
        }
    }
    return false;
}

static int find(int[] root, int x) {
    while (root[x] != x) {
        root[x] = root[root[x]];                     // path halving keeps the trees shallow
        x = root[x];
    }
    return x;
}

Complexity. Time O(E · α(V)) with full union by rank; with path halving alone, as here, it is O(E log V) in the worst case and close to linear in practice. Space O(V) for the parent array. This approach is handy when edges arrive as a stream, since it never needs the whole adjacency list.

Edge cases and pitfalls