Cases Explained | DSU | 100% BEATS | C++ | JAVA | Python
Intuition:
Think of building a tree by adding edges one by one.
If a new edge connects two nodes that are already connected, it creates a cycle.
To track connec
**Intuition:**  
1. Think of building a tree by adding edges one by one.  
2. If a new edge connects two nodes that are *already connected*, it creates a cycle.  
3. To track connections efficiently, we use **DSU (Disjoint Set Union)**.  
4. DSU groups nodes into sets, where each set represents a connected component.  
5. When adding an edge, if the nodes are in the same set, the edge is redundant—it forms a cycle.  
6. The last such edge in the input is the answer.  

---
**Why Return the Last Edge?**  
The problem specifies that if multiple answers exist, return the **last occurrence** in the input. DSU processes edges in order, and the **first detected cycle-causing edge** during this traversal is the one that appears last in the input (since it’s the final piece needed to close the cycle).

---

**How DSU Works with Examples:**

Let’s break it down with symbolic scenarios (`A->B` means connecting nodes A and B):

1. **Case 1: No Cycle (Normal Tree Growth)**  
   - **Edges:** `A-B`, `B-C`, `C-D`  
     - Add `A-B`: A and B are now connected.  
     - Add `B-C`: B (connected to A) and C merge.  
     - Add `C-D`: C (connected to A-B) and D merge.  
   - **Result:** All nodes form a single chain. No cycles.

2. **Case 2: Cycle Detected (Redundant Edge)**  
   - **Edges:** `A-B`, `B-C`, `C-A`  
     - Add `A-B`: Connected.  
     - Add `B-C`: Connected (A-B-C).  
     - Add `C-A`: A and C are already connected! This edge **creates a cycle**.  
   - **Result:** `C-A` is redundant. Return it.

3. **Case 3: Multiple Components Merged**  
   - **Edges:** `X-Y`, `Y-Z`, `W-V`, `V-W` (typo: should be `V-U`?), `Y-W`  
     - Add `X-Y`: Connected.  
     - Add `Y-Z`: Connected (X-Y-Z).  
     - Add `W-V`: New component (W-V).  
     - Add `V-W`: Already connected. Redundant!  
     - **Result:** Return `V-W` (last redundant edge).

4. **Real Example from Problem:**  
   - **Input:** `[[1,2],[1,3],[2,3]]`  
     - Add `1-2`: Connected.  
     - Add `1-3`: Connected (1-2-3).  
     - Add `2-3`: 2 and 3 are already connected via 1. **Cycle formed!**  
   - **Output:** `[2,3]` (last edge in input causing the cycle).

---



**Solution Code:**  
```cpp []
class Solution {
    vector<int> parent;
    vector<int> rank;

    int find(int i) {
        if (parent[i] != i)
            parent[i] = find(parent[i]); // Path compression
        return parent[i];
    }

    void join(int u, int v) {
        int rootU = find(u), rootV = find(v);
        if (rootU != rootV) {
            // Union by rank to balance trees
            if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        
        // Initialize each node as its own parent
        for (int i = 1; i <= n; i++) parent[i] = i;

        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (find(u) == find(v)) return edge; // Cycle detected!
            join(u, v); // Merge sets
        }
        
        return {}; // Unreachable for valid inputs
    }
};
```
``` Java []
class Solution {
    private int[] parent;
    private int[] rank;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];

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

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            if (find(u) == find(v)) {
                return edge; // Cycle detected
            }
            join(u, v); // Merge sets
        }

        return new int[0]; // Unreachable for valid inputs
    }

    private int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // Path compression
        }
        return parent[i];
    }

    private void join(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            // Union by rank
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
}
```
``` Python []
class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        n = len(edges)
        parent = [i for i in range(n + 1)]  # Initialize each node as its own parent
        rank = [0] * (n + 1)  # Rank for union by rank

        def find(i):
            if parent[i] != i:
                parent[i] = find(parent[i])  # Path compression
            return parent[i]

        def join(u, v):
            rootU = find(u)
            rootV = find(v)

            if rootU != rootV:
                # Union by rank
                if rank[rootU] > rank[rootV]:
                    parent[rootV] = rootU
                elif rank[rootU] < rank[rootV]:
                    parent[rootU] = rootV
                else:
                    parent[rootV] = rootU
                    rank[rootU] += 1

        for u, v in edges:
            if find(u) == find(v):
                return [u, v]  # Cycle detected
            join(u, v)  # Merge sets

        return []  # Unreachable for valid inputs
```

**How the Code Works:**  
1. **Initialization:** Every node starts as its own parent.  
2. **For each edge:**  
   - Check if the two nodes are already connected (`find(u) == find(v)`).  
   - If yes: this edge is redundant. Return it immediately.  
   - If no: merge their sets (`join(u, v)`).  
3. **Union-Find Optimizations:**  
   - **Path Compression:** Flattens the structure for faster future queries.  
   - **Union by Rank:** Keeps the tree shallow to optimize `find` operations.  

### **Time Complexity**
The solution efficiently detects the redundant edge in **O(n α(n))** time, which is near-linear. Here, **α(n)** is the inverse Ackermann function, a very slow-growing function that is practically constant for most inputs. This ensures the algorithm is highly efficient even for large graphs.
['Union Find', 'Python', 'C++', 'Java']