JS, Python, Java, C++ | Simple Union-Find Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nIn this problem, the redundant edge will be the one that links together an already-linked graph. To determine whether already-seen segments of the graph have been connected, we can use a simple **union-find** (**UF**) implementation to keep track of the different segments.\n\nWith **UF**, we must define two functions: **union** and **find**. The **find** function will **recursively** trace a node\'s lineage back to its ultimate parent and update its value in the parent array (**par**), providing a shortcut for the next link.\n\nThe **union** function merges two segments by assigning the ultimate parent of one segment to another.\n\nWe can iterate through **edges** and **find** both vertices of the edge to see if they belong to the same segment. If so, we\'ve located our redundant edge and can **return** it. If not, we should merge the two different segments with **union**.\n\n - _**Time Complexity: O(N)** where **N** is the length of **edges**_\n - _**Space Complexity: O(N)** for **par** and the recursion stack_\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **76ms / 41.2MB** (beats 98% / 44%).\n```javascript\nvar findRedundantConnection = function(edges) {\n    let par = Array.from({length: edges.length + 1}, (_,i) => i)\n    const find = x => x === par[x] ? par[x] : par[x] = find(par[x])\n    const union = (x,y) => par[find(y)] = find(x)\n    for (let [a,b] of edges)\n        if (find(a) === find(b)) return [a,b]\n        else union(a,b)\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **44ms / 14.6MB** (beats 99% / 95%).\n```python\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        par = [i for i in range(len(edges) + 1)]\n        def find(x: int) -> int:\n            if x != par[x]: par[x] = find(par[x])\n            return par[x]\n        def union(x: int, y: int) -> None:\n            par[find(y)] = find(x)\n        for a,b in edges:\n            if find(a) == find(b): return [a,b]\n            else: union(a,b)\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **0ms / 39.2MB** (beats 100% / 70%).\n```java\nclass Solution {\n    public int[] findRedundantConnection(int[][] edges) {\n        par = new int[edges.length+1];\n        for (int i = 0; i < par.length; i++)\n            par[i] = i;\n        for (int[] e : edges)\n            if (find(e[0]) == find(e[1])) return e;\n            else union(e[0],e[1]);\n        return edges[0];\n    }\n    private int[] par;\n    private int find(int x) {\n        if (x != par[x]) par[x] = find(par[x]);\n        return par[x];\n    }\n    private void union(int x, int y) {\n        par[find(y)] = find(x);\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **4ms / 8.7MB** (beats 98% / 83%).\n```c++\nclass Solution {\npublic:\n    vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n        par.resize(edges.size()+1);\n        for (int i = 0; i < par.size(); i++)\n            par[i] = i;\n        for (auto& e : edges)\n            if (find(e[0]) == find(e[1])) return e;\n            else uniun(e[0],e[1]);\n        return edges[0];\n    }\nprivate:\n    vector<int> par;\n    int find(int x) {\n        if (x != par[x]) par[x] = find(par[x]);\n        return par[x];\n    }\n    void uniun(int x, int y) {\n        par[find(y)] = find(x);\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']