Beginner Friendly || DSU || Union Find || C++ || Simple Explanation
Intuition\nIf two nodes are already connected then this edge is redundant\n\n# Approach\n- Use union find\n- If the nodes of edge are not already connected, con
# Intuition\nIf two nodes are already connected then this edge is redundant\n\n# Approach\n- Use union find\n- If the nodes of edge are not already connected, connect them (UNION)\n- If they are already connected, it means the current edge is redundant, return this edge\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n```\nclass Solution {\npublic:\n\nint parent[3002]; //to store parent of each node\nint size[3002];   //to store the size of component\n\nvoid make(int v) {   // initializing a component with one node\n    parent[v] = v;\n    size[v] = 1;\n}\n\nint findPar(int a) {    // returns parent of node a\n    if (a == parent[a]) return a;\n    else return parent[a] = findPar(parent[a]);\n}\n\nvoid Union(int a, int b) {   // connects two nodes in one component\n    a = findPar(a);\n    b = findPar(b);\n\n    if (a == b) return;\n\n    if (size[a] < size[b]) {\n        swap(a, b);\n    }\n\n    parent[b] = a;\n    size[a] += size[b];\n}\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        vector<int> ans;\n        int n = edges.size();\n        for (int i = 1; i <= n; i++) make(i);\n        for (int i = 0; i < n; i++) {\n            int u = edges[i][0], v = edges[i][1];\n            int a = findPar(u), b = findPar(v);\n            if (a == b) {   // u and v are already connected, return current edge as it is redundant\n                return {u, v};\n            } else {\n                Union(u, v);  // connects u and v\n            }\n        }\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'C++']