--- Difficulty: Medium Source: 160 Days of Problem Solving Tags: - Graph - Union-Find - DFS --- # πŸš€ _Day 4. Undirected Graph Cycle_ 🧠 The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/graph-gfg-160/problem/detect-cycle-in-an-undirected-graph) ## πŸ’‘ **Problem Description:** Given an **undirected graph** with `V` vertices and `E` edges, represented as a 2D vector `edges[][]`, where each entry `edges[i] = [u, v]` denotes an edge between vertices `u` and `v`, determine whether the graph contains a **cycle** or not. > Note: Sorry for uploading late, my exam is going on. ## πŸ” **Example Walkthrough:** ### **Example 1:** #### **Input:** ``` V = 4, E = 4 edges = [[0, 1], [0, 2], [1, 2], [2, 3]] ``` #### **Output:** ``` True ``` #### **Explanation:** There exists a cycle: **1 β†’ 2 β†’ 0 β†’ 1** ### **Example 2:** #### **Input:** ``` V = 4, E = 3 edges = [[0, 1], [1, 2], [2, 3]] ``` #### **Output:** ``` False ``` #### **Explanation:** No cycle exists in the given graph. ### **Constraints:** - $1 \leq V \leq 10^5$ - $1 \leq E = \text{edges.size()} \leq 10^5$ ## 🎯 **My Approach:** ## **Optimized Approach: Union-Find with Path Compression** ### **Algorithm Steps:** 1. **Initialize a parent array** where each node is its own parent (`-1`). 2. **Find function with path compression** to efficiently determine the representative parent of each node. 3. **Union function with union by size** to merge sets efficiently. 4. **Iterate over all edges** and apply union-find: - If both nodes of an edge belong to the same set, a **cycle is detected**. - Otherwise, perform a **union operation** to merge them. 5. **Return true if a cycle is found, otherwise return false**. ## πŸ•’ **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** `O(E * Ξ±(V))`, where `Ξ±(V)` is the inverse Ackermann function, which grows extremely slowly and is nearly constant. - **Expected Auxiliary Space Complexity:** `O(V)`, as we store only the parent array. ## πŸ“ **Solution Code** ## **Code (C++)** ```cpp class Solution { public: bool isCycle(int V, vector>& edges) { vector p(V, -1); function f = [&](int x){ return p[x] < 0 ? x : p[x] = f(p[x]); }; for(auto &e : edges){ int a = f(e[0]), b = f(e[1]); if(a == b) return true; if(p[a] > p[b]) swap(a, b); p[a] += p[b]; p[b] = a; } return false; } }; ```

⚑ Alternative Approaches

 ## πŸ“Š **1️⃣ DFS Based Cycle Detection Approach** #### **Algorithm Steps:** 1. Build an adjacency list from the edge list. 2. Use a DFS traversal to detect a cycle by marking visited nodes and ensuring that a visited neighbor (other than the parent) is detected. ```cpp class Solution { public: bool dfs(int u, int parent, vector>& g, vector& vis) { vis[u] = true; for (int v : g[u]) if (!vis[v] ? dfs(v, u, g, vis) : v != parent) return true; return false; } bool isCycle(int V, vector>& edges) { vector> g(V); for (auto &e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); } vector vis(V, false); for (int i = 0; i < V; i++) if (!vis[i] && dfs(i, -1, g, vis)) return true; return false; } }; ``` #### πŸ“ **Complexity Analysis:** - **Time Complexity:** `O(V + E)` - **Space Complexity:** `O(V + E)` #### βœ… **Why This Approach?** This DFS approach is intuitive for many graph problems. It clearly separates the concept of a visited node and its parent, making it straightforward to detect back edges that indicate cycles. ## πŸ“Š **2️⃣ Union-Find (Iterative Path Compression) Approach** #### **Algorithm Steps:** 1. Initialize a parent array with `-1` for all vertices. 2. For each edge, find the roots iteratively. 3. Merge the sets if roots are different; if not, a cycle exists. ```cpp class Solution { public: int find(vector& p, int x) { while(p[x] >= 0) x = p[x]; return x; } bool isCycle(int V, vector>& edges) { vector p(V, -1); for(auto &e : edges){ int a = find(p, e[0]), b = find(p, e[1]); if(a == b) return true; if(p[a] > p[b]) swap(a, b); p[a] += p[b]; p[b] = a; } return false; } }; ``` #### πŸ“ **Complexity Analysis:** - **Time Complexity:** `O(E * Ξ±(V))` (Ξ± is the inverse Ackermann function) - **Space Complexity:** `O(V)` #### βœ… **Why This Approach?** The Union-Find structure with iterative path compression is highly efficient for cycle detection when the graph is provided as an edge list. ### πŸ†š **Comparison of Approaches** | **Approach** | ⏱️ **Time Complexity** | πŸ—‚οΈ **Space Complexity** | βœ… **Pros** | ⚠️ **Cons** | | ---------------------------------------------- | ---------------------- | ----------------------- | -------------------------------------------- | ------------------------------------------------- | | **Union-Find (Recursive Path Compression)** | 🟒 O(E \* Ξ±(V)) | 🟑 O(V) | Efficient for edge-list input, compact code. | Recursion depth may be an issue for large graphs. | | **DFS-Based Cycle Detection (Adjacency List)** | 🟒 O(V + E) | 🟑 O(V) | Simple, intuitive cycle detection method. | Requires adjacency list construction. | | **Union-Find (Iterative Path Compression)** | 🟒 O(E \* Ξ±(V)) | 🟑 O(V) | Avoids recursion, better readability. | Slightly more verbose than recursive version. | βœ… **Best Choice?** - **Union-Find (Recursive Path Compression)** is the most efficient when edges are given as an edge list. - **Union-Find (Iterative Path Compression)** is preferred when recursion is not suitable. - **DFS-Based Cycle Detection** is best when the graph is naturally stored as an adjacency list.
## **Code (Java)** ```java class Solution { public boolean isCycle(int V, int[][] edges) { int[] p = new int[V]; Arrays.fill(p, -1); for (int[] e : edges) { int a = f(p, e[0]), b = f(p, e[1]); if (a == b) return true; if (p[a] > p[b]) { int t = a; a = b; b = t; } p[a] += p[b]; p[b] = a; } return false; } int f(int[] p, int x) { return p[x] < 0 ? x : (p[x] = f(p, p[x])); } } ``` ## **Code (Python)** ```python class Solution: def isCycle(self, V, edges): p = [-1]*V def f(x): return x if p[x]<0 else f(p[x]) for u,v in edges: a, b = f(u), f(v) if a == b: return True if p[a] > p[b]: a,b = b,a p[a] += p[b]; p[b] = a return False ``` ## 🎯 **Contribution and Support:** For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ **If you find this helpful, please give this repository a star!** ⭐ ---

πŸ“Visitor Count