Redundant Connection [C++]
IntuitionThe problem requires us to find an extra edge in a connected undirected graph that makes it cyclic. This means that all nodes are already connected, an
### **Intuition**
The problem requires us to find an extra edge in a connected undirected graph that makes it cyclic. This means that all nodes are already connected, and adding one more edge creates a cycle. 

A **Disjoint Set Union (DSU) / Union-Find** structure is well-suited for detecting cycles in an undirected graph. The key observation is:
- If two nodes are already connected (i.e., belong to the same component), then adding an edge between them will form a cycle.

### **Approach**
We use the **Union-Find** data structure with **Path Compression** and **Union by Rank** to efficiently detect cycles in the graph:
1. **Initialize** the parent array where each node is its own parent and the rank array to manage tree depth.
2. **Iterate through the edges** and perform `union` operations:
   - If both nodes of an edge are already in the same connected component (i.e., they have the same root in the DSU structure), we have found the redundant edge.
   - Otherwise, merge the sets using `union by rank`.
3. **Return the first edge that causes a cycle**.

### **Complexity Analysis**
- **Time Complexity**: \(O(N \alpha(N)) \approx O(N)\)  
  - Each `find()` and `union()` operation runs in almost **constant time** \(O(\alpha(N))\), where \(\alpha(N)\) is the **inverse Ackermann function**, which grows extremely slowly.
  - We iterate over all edges, so the total complexity is close to **O(N)**.
  
- **Space Complexity**: \(O(N)\)  
  - We store two arrays (`parent` and `rank`), each of size \(O(N)\).

---

### **Code**
```cpp
class Solution {
public:
    vector<int> parent, rank;

    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    bool unionSet(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] > rank[rootY]) swap(rootX, rootY);
        parent[rootX] = rootY;
        if (rank[rootX] == rank[rootY]) rank[rootY]++;
        return true;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);

        for (const auto& edge : edges) {
            if (!unionSet(edge[0], edge[1])) {
                return edge;
            }
        }

        return {};
    }
};
```

### **Why This Works Well**
✅ **Path compression in `find()`** makes lookups faster by flattening the tree.  
✅ **Union by rank** keeps the tree shallow, reducing unnecessary merging.  
✅ **Iterating over edges once** ensures we return the first redundant edge in **O(N) time**.  

🚀 **This is an optimal solution for cycle detection in an undirected graph using DSU!**
['C++']