Very well explained 4ms C++ solution (disjoint set) with an example
This solution uses disjoint set or union-find method. \n\nLet\'s take the following example and see how the code works.\n\n\n[[1,2], [1,3], [2,3]]\n\n\t      1\
This solution uses disjoint set or union-find method. \n\nLet\'s take the following example and see how the code works.\n\n```\n[[1,2], [1,3], [2,3]]\n\n\t      1\n\t\t / \\\n\t\t2 - 3\n```\n\nThe parent subset array created is as follows. The 0 slot is not used. By -1 we mean that each vertex stands on its own and parents have not been determined yet.\n\n```\n 0   1   2   3  \n-1  -1  -1  -1\n```\n\nFor edge [1,2] - find(ss, 1) returns 1, find(ss, 2) returns 2. Since both are not equal, we unionize them as follows:\n\n```\n 0   1   2   3  \n-1  -1   1  -1\n\nIt means, "we made the vertex 1 a parent of 2"\n```\n\nFor edge [1,3] - find(ss, 1) returns 1, find(ss, 3) returns 3. Since both are not equal, we unionize them as follows:\n\n```\n 0   1   2   3  \n-1  -1   1   1\n\nIt means, "we made the vertex 1 a parent of 3"\n```\n\nNow comes the edge [2, 3] - find(ss, 2) returns 1 and find(ss, 3) returns 1. Both are equal => this edge is causing the cycle and it must be the answer.\n\n```\n/* LeetCode: tktripathy */\nclass Solution {\npublic:\n    /*\n     * Find the subset a vertex belongs to.\n     */\n    int find(vector<int> &ss, int x) {\n        if (ss[x] == -1) return x;\n        return find(ss, ss[x]);\n    }\n    \n    /*\n     * Unionize two subsets. \n     */\n    void _union(vector<int> &ss, int x, int y) {\n        int xp = find(ss, x);\n        int yp = find(ss, y);\n        if (xp != yp) ss[yp] = xp;\n    }\n    \n    /*\n     * We use disjoint set (or Union-Find) to detect a cycle in\n     * an undirected graph.\n     */\n    vector<int> findRedundantConnection(vector<vector<int> >& e/*dges*/) {\n        \n        /* Create parent subsets and initialize them to -1 - this means\n         * the subsets contain only one item - i.e ss[i] only contains\n         * vertex i.\n         */\n        vector<int> ss; ss.push_back(-1);\n        for (int i = 0; i < e.size(); i++) ss.push_back(-1);\n        \n        /*\n         * We go through each edge one by one. We find the subset\n         * that the vertices of an edge belongs to. If they belong\n         * to two different subsets, we merge them into one set \n         * using Union. Now, if both vertices are in the same \n         * subset, we got a cycle - we return it.\n         *\n         */\n        for (int i = 0; i < e.size(); ++i) {\n            int x = find(ss, e[i][0]), y = find(ss, e[i][1]);            \n            if (x == y) return { e[i][0], e[i][1] };\n            _union(ss, x, y);\n        }\n        \n        /* No redundant edge found */\n        return vector<int>();\n    }\n};\n```
[]