Solution: Redundant Connection
Tags: algorithms, javascript, java, python
Published: 2021-06-25 08:37:14

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/redundant-connection/discuss/1295728).*

---

#### [Leetcode Problem #684 (*Medium*): Redundant Connection](https://leetcode.com/problems/redundant-connection/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
In this problem, a tree is an **undirected graph** that is connected and has no cycles.
>
You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two **different** vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the graph.
>
Return an edge that can be removed so that the resulting graph is a tree of `n` nodes. If there are multiple answers, return the answer that occurs last in the input.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| edges = [[1,2],[1,3],[2,3]]
Output:| [2,3]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg)
>
Example 2:||
|---:|---|
Input:| edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output:| [1,4]
Visual:|![Example 2 Visual](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg)

---

#### ***Constraints:***
>
 - `n == edges.length`
 - `3 <= n <= 1000`
 - `edges[i].length == 2`
 - `1 <= ai < bi <= edges.length`
 - `ai != bi`
 - There are no repeated edges.
 - The given graph is connected.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

In 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.

With **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.

The **union** function merges two segments by assigning the ultimate parent of one segment to another.

We 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**.

 - _**Time Complexity: O(N)** where **N** is the length of **edges**_
 - _**Space Complexity: O(N)** for **par** and the recursion stack_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findRedundantConnection = function(edges) {
    let par = Array.from({length: edges.length + 1}, (_,i) => i)
    const find = x => x === par[x] ? par[x] : par[x] = find(par[x])
    const union = (x,y) => par[find(y)] = find(x)
    for (let [a,b] of edges)
        if (find(a) === find(b)) return [a,b]
        else union(a,b)
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        def find(x: int) -> int:
            if x != par[x]: par[x] = find(par[x])
            return par[x]
        def union(x: int, y: int) -> None:
            par[find(y)] = find(x)
        for a,b in edges:
            if find(a) == find(b): return [a,b]
            else: union(a,b)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        par = new int[edges.length+1];
        for (int i = 0; i < par.length; i++)
            par[i] = i;
        for (int[] e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else union(e[0],e[1]);
        return edges[0];
    }
    private int[] par;
    private int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    private void union(int x, int y) {
        par[find(y)] = find(x);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        par.resize(edges.size()+1);
        for (int i = 0; i < par.size(); i++)
            par[i] = i;
        for (auto& e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else uniun(e[0],e[1]);
        return edges[0];
    }
private:
    vector<int> par;
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    void uniun(int x, int y) {
        par[find(y)] = find(x);
    }
};
```