✅ Easy to Understand | 100% Faster | Disjoint Set Union | Detailed Video explanation 🔥
IntuitionThe problem requires us to find a redundant edge in a connected undirected graph. A redundant edge means that if we remove it, the graph remains connec
# Intuition
The problem requires us to find a redundant edge in a connected undirected graph. A redundant edge means that if we remove it, the graph remains connected.  
Since the graph initially forms a tree (which has **n nodes and n-1 edges**), adding an extra edge will always create a **cycle**.  
Thus, the problem boils down to detecting the first edge that forms a cycle in the given sequence.  

A **Union-Find (Disjoint Set)** data structure is an efficient way to detect cycles in an undirected graph.  
By iterating through all edges and checking whether two nodes are already connected, we can determine the redundant edge.

---

# Approach
1. **Use Union-Find (Disjoint Set) to track connected components.**
2. **For each edge \([u, v]\):**
   - Use the **find()** function to determine the root parent of `u` and `v`.
   - If `find(u) == find(v)`, adding this edge creates a cycle → **Return the edge**.
   - Otherwise, use the **union()** function to merge the components.
3. **Return the redundant edge that caused a cycle.**

### **Union-Find Implementation**
- **Find with Path Compression**: This optimizes the `find()` function by flattening the tree structure, making future lookups faster.
- **Union without Rank Optimization**: This version only assigns the parent but does not balance the tree depth.

---

# Complexity
- **Time Complexity**:  
  - The **find()** and **union()** operations are nearly **constant time** \( O(\alpha(n)) \), where \( \alpha(n) \) is the inverse Ackermann function.
  - Since we process **n edges**, the total complexity is **\( O(n) \)**.

- **Space Complexity**:  
  - We maintain a **parent array** of size \( O(n) \).
  - No extra space is used apart from this, so the overall space complexity is **\( O(n) \)**.


# Code
```java []
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);

        for(int[] edge: edges){
            if( ! uf.union(edge[0]-1, edge[1]-1) ){
                return edge;
            }
        }

        return new int[]{};     // won't reach here as per problem.
    }

    static class UnionFind {
        int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            Arrays.fill(parent, -1);        // no parent, single node currently in component, khud ka parent
        }

        public int find(int x) {
            if (parent[x] == -1) {
                return x;
            }
            return parent[x] = find(parent[x]);       // pruning , path compression
        }

        public boolean union(int a, int b) {
            a = find(a);
            b = find(b);
            if (a != b) {
                parent[a] = b;
                return true;    
            }
            return false;       // already part of one component. 
        }
    }
}
```

LeetCode 684 Redundant Connection | Disjoint Set Union | Graph Theory Essential
https://youtu.be/oHNaJFk6qdg


['Union Find', 'Graph', 'Java']