684. Redundant Connection

class UnionFind {
    private:
        vector<int> parent;
        vector<int> rank;
    public:
        UnionFind(int n) {
            parent.resize(n + 1);
            rank.resize(n + 1);
            for (int i = 0; i <= n; ++i) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        int find(int x) {
            if(parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void merge(int n1, int n2) {
            int p1 = find(n1);
            int p2 = find(n2);

            if(p1 == p2) return;

            if(rank[p1] > rank[p2]) {
                parent[p2] = p1;
                rank[p1] += rank[p2];
            } else {
                parent[p1] = p2;
                rank[p2] += rank[p1];
            }
        }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UnionFind uf(n);
        for (const auto& edge : edges) {
            if (uf.find(edge[0]) == uf.find(edge[1])) {
                return edge;
            }
            uf.merge(edge[0], edge[1]);
        }
        return {};
    }
};

• T: $O(N)$
• S: $O(N)$