BEATS 100% USERS
IntuitionThe intuition was to return the edge which was already connected to the component.Example:-Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]Let's say a
# Intuition
The intuition was to return the edge which was already connected to the component.Example:-

**Input**: edges = [[1,2],[1,3],[2,3]]
**Output**: [2,3]

**Let's say a = [1, 2], b = [1, 3], c = [2, 3]**

Starting from "a" 1 gets connected to 2, then in "b" 1 gets connected to 3, so 3 is also connected to 2, then coming to "c" as 2 is already connected to 3 we return this edge.

# Approach
As we are using the concept of connecting components we will be using Disjoint Sets.
In this particular problem i have used **Union by Size**

# Complexity
- Time complexity:
Find: α(n) is the Inverse Ackermann function (almost constant).
Union: O(α(n)) due to Union by Size.
**Overall Time Complexity = O(n)**

- Space complexity:
O(n)

# Code
```cpp []
class Solution {
public:

    vector<int> parent;
    vector<int> size;

    int findParent(int x){
        if(parent[x] == x) return x;

        return parent[x] = findParent(parent[x]);
    }

    void UnionBySize(int x, int y){//Join components on based of size
        int parent_x = findParent(x);
        int parent_y = findParent(y);

        if(size[parent_x] > size[parent_y]){
            parent[parent_y] = parent_x;
            size[parent_x] += size[parent_y];
        }
        else{
            parent[parent_x] = parent_y;
            size[parent_y] += size[parent_x];   
        }
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        
        int n = edges.size();
        parent.resize(n);
        size.resize(n, 1);

        for(int i = 0; i < n; i++){
            parent[i] = i;
        }

        for(const auto&edge : edges){
            //As Edges are from 1 to n , for our indexing we will subtract 1
            int x = edge[0] - 1;
            int y = edge[1] - 1;

            int parent_x = findParent(x);
            int parent_y = findParent(y);

            if(parent_x == parent_y){//Component is already connected
                return edge;
            }else{//Join the Components
                UnionBySize(x, y);
            }
        }

        return {};
    }
};
```
['Union Find', 'Graph', 'C++']