684

class Solution {
vector<int> parent, rank;
public:
    int findParent(int x){
        return (parent[x] == x) ? x: (parent[x] = findParent(parent[x]));
    }

    void unionSet(int x, int y){
        int px = findParent(x);
        int py = findParent(y);
        if(px != py){
            if(rank[px] > rank[py]){
                parent[py] = px;
            }
            else{
                parent[px] = py;
                if(rank[px] == rank[py]) rank[py]++;
            }
        }
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n+1); rank.resize(n+1);
        for(int i=1; i<=n; i++)
            parent[i] = i;

        for(auto edge: edges){
            if(findParent(edge[0]) == findParent(edge[1]))
                return edge;
            unionSet(edge[0], edge[1]);
        }
        return edges[n-1];
    }
};