Union-Find ✅ | Beats 100%🔥| Detailed Explanation Solution ✅
🔗 Redundant Connection - Java Solution 🏗️📜 Problem StatementGiven a graph with N nodes, we have N edges forming an undirected tree. However, there's one extra e
---

# 🔗 **Redundant Connection** - Java Solution 🏗️

---

## 📜 **Problem Statement**  

Given a graph with **N** nodes, we have `N` edges forming an **undirected tree**. However, there's **one extra edge**, making the graph **cyclic**.

Your task is to **find and remove that extra edge** so that the remaining graph is a **tree**.

✅ The graph consists of **N nodes labeled from `1` to `N`**.  
✅ There will always be **exactly one redundant connection**.  
✅ Return the **edge that, when removed, leaves a tree**.  
✅ If multiple answers exist, return the edge **that appears last** in the input.

---

## 🧠 **Understanding the Problem with an Example**

### **Input**
```plaintext
edges = [[1,2], [1,3], [2,3]]
```

### **Graph Representation**  
Before removing any edge, the graph looks like this:

```
    1
   / \
  2 - 3
```

### **Expected Output**
```plaintext
[2,3]
```
Removing `[2,3]` makes it a valid **tree**.

---

## 🔥 **Approach: Union-Find (Disjoint Set)**
### ✨ **Why Use Union-Find?**
Union-Find is a **powerful** data structure used to detect **cycles** in an **undirected graph** efficiently.

### ✅ **Key Idea**
- If **two nodes are already connected** and we try to add an edge **between them**, it **creates a cycle**. 🚨  
- The first such edge in the list is our **answer**!  

### 🔑 **Steps to Solve the Problem**
1️⃣ **Initialize a Parent Array**:  
   - `p[i]` stores the parent of node `i`.  
   - Initially, each node is its **own parent** (`p[i] = i`).  

2️⃣ **Use Path Compression for Union-Find**:  
   - For every edge `[u, v]`, **find their root parents**.  
   - If they have the **same root**, the edge is **redundant**.  
   - Otherwise, **union** them by making one parent of the other.  

---

## 💻 **Java Code**
```java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1]; // Parent array

        // Initialize parent array: each node is its own parent
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int[] ans = {0, 0}; // Store the redundant edge

        for (int[] edge : edges) {
            int p1 = find(parent, edge[0]); // Find root of first node
            int p2 = find(parent, edge[1]); // Find root of second node

            if (p1 == p2) {
                ans = edge; // If they have the same root, this edge is redundant
            } else {
                parent[p2] = p1; // Union: connect p2 to p1
            }
        }
        return ans;
    }

    // Union-Find with Path Compression
    private int find(int[] parent, int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]]; // Path compression
            node = parent[node];
        }
        return node;
    }
}
```

---

## 🧩 **Step-by-Step Execution**
Let’s walk through an example to see how this works!

### **Example**
```plaintext
edges = [[1,2], [1,3], [2,3]]
```

### **Initialization**
```plaintext
parent[] = [0, 1, 2, 3]   (Each node is its own parent)
```

### **Processing Edges**
1️⃣ **Processing `[1,2]`**  
   - Find `parent(1) = 1`, `parent(2) = 2`.  
   - Since they have **different parents**, merge them.  
   - `parent[2] = 1`.  
   - **Updated Parent Array**: `[0, 1, 1, 3]`.

2️⃣ **Processing `[1,3]`**  
   - Find `parent(1) = 1`, `parent(3) = 3`.  
   - Merge them: `parent[3] = 1`.  
   - **Updated Parent Array**: `[0, 1, 1, 1]`.

3️⃣ **Processing `[2,3]`**  
   - Find `parent(2) = 1`, `parent(3) = 1`.  
   - **They have the same root!** 🚨 **Cycle detected!**  
   - **Redundant edge is `[2,3]`**.

### **Final Output**
```plaintext
[2,3]
```

---

## 📊 **Time and Space Complexity**
| Complexity | Value |
|------------|-------|
| 🕒 Time Complexity | **O(N α(N)) ≈ O(N)**  *(Almost linear due to path compression)* |
| 🗄 Space Complexity | **O(N)** *(For parent array storage)* |

---

## 🔥 **Why is This Approach Efficient?**
✅ **Avoids building an explicit graph** (no adjacency list).  
✅ **Path compression ensures** nearly constant time `find()` operations.  
✅ **Runs in almost linear time**: **O(N)** (because of the inverse Ackermann function `α(N)`).  

---

## 🎯 **Summary**
- ✅ Used **Union-Find** to detect cycles efficiently.
- ✅ **Path Compression** ensures optimal time complexity.
- ✅ **Finds the last redundant edge**, which, when removed, leaves a valid tree.
- ✅ Works in **O(N)** time.

---

## 🎉 **Final Thoughts**
💡 **Mastering Union-Find is crucial for graph problems!**  
📌 This problem is a great **practice for cycle detection** and **graph connectivity**.  

---

**🙌🏻 If this solution and explanation helped, consider upvoting! Let’s ace those coding challenges together!** ✨
['Union Find', 'Graph', 'Java']