16-Detect-Cycle-in-Undirected-Graph.md

Detect Cycle in Undirected Graph

Problem Link

Practice Problem

---

Pattern

• DFS
• Union-Find

---

Approach

Track the parent of each DFS call and detect revisiting a visited node that is not the parent.

---

Time Complexity

O(V + E)

Space Complexity

O(V)

---

Java Solution

import java.util.*;
class Solution {
    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dfs(i, -1, adj, visited)) return true;
        }
        return false;
    }

    private boolean dfs(int node, int parent, ArrayList<ArrayList<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                if (dfs(next, node, adj, visited)) return true;
            } else if (next != parent) {
                return true;
            }
        }
        return false;
    }
}