Lesson 23.1 · Cycle Detection

Cycles in Undirected Graphs

During DFS or BFS, an edge to a visited node that isn't your parent closes a cycle. Union-find spots it as an edge whose endpoints are already in the same group.

12 min

Think of it like this

Walking around a neighbourhood leaving chalk marks: if you find your own chalk on a street you didn't just come from, the streets form a loop.

1.Two ways

Traversal with parent: in DFS/BFS from u, for each neighbour v: if v is unvisited, visit it with parent u; if v is visited and v ≠ parent, there's a cycle. (The parent check matters because every undirected edge appears in both directions.)

Union-find: process edges one by one; if both endpoints already have the same root, this edge connects two nodes that were already connected, so it closes a cycle. Otherwise union them.

A connected undirected graph with n nodes is a tree exactly when it has n − 1 edges and no cycle.

Main.java

import java.util.Arrays;

public class Main {
    static int[] parent;

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

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 1}};
        parent = new int[4];
        for (int i = 0; i < 4; i++) parent[i] = i;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) { System.out.println("edge " + Arrays.toString(e) + " closes a cycle"); continue; }
            parent[a] = b;
            System.out.println("union " + Arrays.toString(e));
        }
    }
}

Output

union [0, 1]
union [1, 2]
union [2, 3]
edge [3, 1] closes a cycle

Remember

Visited and not the parent → cycle.
Union-find: same root before union → cycle.
Tree = connected + n − 1 edges.

Common mistakes

Forgetting the parent exception (every edge looks like a cycle).
Using the undirected check on a directed graph.

Command Palette

Cycles in Undirected Graphs

1.Two ways