Undirected Graph Cycle

Time: O(V+E)

Space: O(V)

Intuition

BFS or DFS with parent tracking. In an undirected graph, a cycle exists if a visited neighbor is not the direct parent. Track the parent to avoid treating the back-edge to parent as a cycle.

Algorithm

1DFS(node, parent): for each neighbor v: if !visited: DFS(v, node). Else if v != parent: cycle detected.

Example Walkthrough

Input: Graph: 0-1, 1-2, 2-0 (triangle)

1.DFS(0,âˆ’1)â†’DFS(1,0)â†’DFS(2,1): neighbor 0 is visited and â‰ parent(1) â†’ cycle!

Output: true

Common Pitfalls

•Pass parent as -1 for the root node. For multigraphs (parallel edges), use parent-edge ID instead of parent node.

Undirected Graph Cycle.java

Java

// Approach: DFS/BFS with parent tracking. A cycle exists if a visited non-parent neighbor is found.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    public boolean isCycle(int V, int[][] edges) {
        // Code here
        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        boolean[] vis = new boolean[V];

        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                if (bfsCheck(i, adj, vis))
                    return true;
            }
        }

        return false;
    }

    private boolean bfsCheck(int src, List<List<Integer>> adj, boolean[] vis) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { src, -1 });
        vis[src] = true;

        while (!q.isEmpty()) {
            int[] node = q.poll();
            int curr = node[0];
            int parent = node[1];

            for (int neighbor : adj.get(curr)) {
                if (!vis[neighbor]) {
                    vis[neighbor] = true;
                    q.offer(new int[] { neighbor, curr });
                } else if (neighbor != parent)
                    return true;
            }
        }

        return false;
    }
}

Was this solution helpful?