Detect Cycle in Undirected Graph

Problem Statement

You’re a graph investigator checking an undirected graph for cycles. Given vertices and edges, return true if a cycle exists, false otherwise. This medium-level DFS challenge is a loop hunt—track parents to spot back edges!

Example

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

Graph:

0---1
    |   |
    |   |
    3---2

Output: true (1-2-3-1 cycle)

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

Output: false (Tree, no cycle)

Code

class Solution {
    public boolean hasCycle(int V, int[][] edges) {
        List> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dfs(graph, i, -1, visited)) return true;
        }
        return false;
    }
    private boolean dfs(List> graph, int node, int parent, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                if (dfs(graph, neighbor, node, visited)) return true;
            } else if (neighbor != parent) {
                return true; // Back edge
            }
        }
        return false;
    }
}
            

from collections import defaultdict
def has_cycle(V, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * V
    def dfs(node, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    for i in range(V):
        if not visited[i] and dfs(i, -1):
            return True
    return False
            

function hasCycle(V, edges) {
    let graph = Array(V).fill().map(() => []);
    for (let [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    let visited = new Array(V).fill(false);
    function dfs(node, parent) {
        visited[node] = true;
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, node)) return true;
            } else if (neighbor !== parent) {
                return true;
            }
        }
        return false;
    }
    for (let i = 0; i < V; i++) {
        if (!visited[i] && dfs(i, -1)) return true;
    }
    return false;
}
            

Explanation

• DFS Insight: Cycle exists if a visited node isn’t the parent—indicates a back edge.
• Flow: Build graph, DFS with parent tracking, check for non-parent visited nodes.
• Example Walkthrough: [0,1],[1,2],[2,0] → 0→1→2→0 (not parent) → true.
• Union-Find Alt: Merge edges, detect if already connected—O(V) space.
• Disconnected Graphs: Check all components to ensure full coverage.

Note