C++ solution | union find | easy short code
\n\n\tclass Solution {\n\tpublic:\n    \n    int parent(int i, vector &p)\n    {\n        if(p[i]==i)\n        {\n            return i;\n        }\n        \n  
\n\n\tclass Solution {\n\tpublic:\n    \n    int parent(int i, vector<int> &p)\n    {\n        if(p[i]==i)\n        {\n            return i;\n        }\n        \n       return parent(p[i],p);\n    }\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        \n        int n = edges.size();\n        vector<int> p(n+1);\n        vector<int> ans;\n        \n        for(int i=0;i<n+1;i++)\n        {\n            p[i]=i;\n        }\n        \n        for(int i=0;i<n+1;i++)\n        {\n            int a = parent(edges[i][0], p);\n            int b = parent(edges[i][1], p);\n            \n            if(a != b)\n            {\n                p[a] = b;\n            }\n            else\n            {\n                ans.push_back(edges[i][0]);\n                ans.push_back(edges[i][1]);\n                break;\n            }\n            \n        }\n        \n        return ans;\n        \n    }\n};\n\n\nEasy and very short code , Using union-find algorithm \nstep 1 : make  a parent array having ith node as its own parent \nstep 2: iterate over the array of edges one by one \nstep 3: for ith edge , find parent of both the node and if both the parents are not equal make any one, parent of other. repeat that until u find the edge having same parent which means that edge is making a cycle and to make the graph a tree , we have to remove that node which is our ans.
['Graph']