Cycle In Undirected Graph
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/ * ============================================================================================ * PROBLEM: Cycle in Undirected Graph * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an undirected graph with A nodes and M edges. * Determine if the graph contains at least one cycle. * - A cycle must contain at least three nodes. * - The graph may consist of multiple disconnected components. * - Return 1 if a cycle exists, else 0. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * In an undirected graph, a cycle exists if during a traversal (DFS or BFS), we encounter * a node that has already been visited, and that node is NOT the immediate parent of * the current node. * * Algorithm (DFS): * 1. Build an adjacency list to represent the graph. * 2. Use a 'visited' array to keep track of processed nodes. * 3. Since the graph may be disconnected, iterate through all nodes from 1 to A. * 4. If a node is not visited, start a DFS: * DFS(node, parent): * - Mark 'node' as visited. * - For each 'neighbor' of 'node': * - If 'neighbor' is NOT visited: * - Recursively call DFS(neighbor, node). * - If recursion returns 1, a cycle is found. * - Else if 'neighbor' is visited AND 'neighbor' != parent: * - This means we found a back-edge to an ancestor that isn't the parent. * - A cycle is detected. Return 1. * 5. If no DFS call returns 1, return 0. * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= A <= 10^5 * 1 <= M <= min(A(A-1)/2, 10^5) * * Time Complexity: * O(A + M) - We visit every node and every edge once across all components. * * Space Complexity: * O(A + M) - To store the adjacency list and the recursion stack. * * --------------------- * 4. Example * --------------------- * Input: A = 3, B = [[1, 2], [2, 3], [3, 1]] * 1 -> 2 * 2 -> 3 * 3 -> 1 (Visited, not parent of 3) -> CYCLE FOUND. * ============================================================================================ / public class CycleInUndirectedGraph { public int solve(int A, int[][] edges5) { // TODO: Implement solution return 0; } }