# 684. Redundant Connection

### Leetcode

<https://leetcode.com/problems/redundant-connection/description/>

### 題目

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg)

<pre><code><strong>Input: edges = [[1,2],[1,3],[2,3]]
</strong><strong>Output: [2,3]
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg)

<pre><code><strong>Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
</strong><strong>Output: [1,4]
</strong></code></pre>

### 前置知識 - Union-Find 算法 <a href="#ti-jie" id="ti-jie"></a>

{% embed url="<https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/UnionFind%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3.md>" %}

### **說明** <a href="#ti-jie" id="ti-jie"></a>

題目給出的是一個環形相連的樹狀結構，`edges` 代表著相連的邊界，但其中會有一條邊界刪掉後就可以避免樹狀結構環形相連

範例：`edges = [[1,2],[1,3],[2,3]]`

最後 `[2, 3]` 節點連在一起的話，會導致整體結構變環形，因此需要刪掉的就是最後一條會導致環形的 `[2, 3]` edge

### 解答

* **方法一 - Union find**

```javascript
var findRedundantConnection = function (edges) {
    const parent = Array.from({ length: edges.length + 1 })
        .map((_, index) => index)

    function find(index) {
        while (index !== parent[index]) {
            index = parent[index];
        }
        return index
    }

    function union(u, v) {
        let rootU = find(u);
        let rootV = find(v);
        if (rootU === rootV) {
            return true;
        }
        parent[rootU] = rootV;
    }

    for (let edge of edges) {
        const [u, v] = edge;
        const isUnion = union(u, v)
        if (isUnion) return [u, v];
    }

    return []
};
```

**參考資料**

{% embed url="<https://www.youtube.com/watch?v=4hJ721ce010>" %}

{% embed url="<https://medium.com/traveling-light-taipei/leetcode-684-redundant-connection-javascript-cffd16ba9cbc>" %}
