---
# System prepended metadata

title: 684. Redundant Connection
tags: [Leetcode, medium, python, union find, c++, graph]

---

###### tags: `Leetcode` `medium` `union find` `graph` `python` `c++`

# 684. Redundant Connection

## [題目連結:] https://leetcode.com/problems/redundant-connection/

## 題目:
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.

![](https://i.imgur.com/AGPxPCu.png)
![](https://i.imgur.com/yospINz.png)

## 解題想法:
* 此題介紹說**樹**為一個連通且無還的**無向**圖
    * 輸入一個圖，含N個節點(1~N)及N條邊
        * 節點不重複
        * 邊不重複
        * 邊:[u,v]表示連接點u與v的無向邊
    * **返回一條可以刪除的邊**，使得結果變成有N個節點的樹
        * 若有多個答案，則返回數組中最後出線的邊

* Use Union Find: time O(n)
    * 字典紀錄每個節點與其對應的parent
        * key為該node
        * value為該node的parent
        * 初始: parent皆為node自己
        ``` python=
        parent=defaultdict(int)
        for i in range(1,len(edges)+1):
            parent[i]=i 
        ```
    * 逐一遍歷所有邊
        ``` python=
        for u,v in edges:
            parentOfU=self.find(u,parent)
            parentOfV=self.find(v,parent)
        ```
    * 判斷當前的邊是否為冗員
        * case1: Union
            * if parentOfU!=parentOfV:
                * 將parentOfV的parent改為parentOfU
                * parent[parentOfV]=parentOfU
        * case2: 冗員
            * 否則兩者祖先一樣:
                * 表是當前的邊可以被先前的組合取代了
                * return [ u , v ]

    * 額外函式: **find(node, parent)**
        * 目的: 回傳該節點的parent
        * if parent[node]==node:
            * 表示parent為該node自己
            * 代表只有自己一點
            * 所以 return node自己即可
        * else:
            * 遞迴求解 root=find(parent[node], parent)
            * return root


## Python:
``` python=
from collections import defaultdict
class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        #use Union Find=> time:O(n)
        #找最後一條邊 該邊加入會導致形成cycle
        parent=defaultdict(int)
        #初始: parent皆為自己
        for i in range(1,len(edges)+1):
            parent[i]=i #key為node  value為該node的parent
        #遍歷
        for u,v in edges:
            parentOfU=self.find(u,parent)
            parentOfV=self.find(v,parent)
            if parentOfU!=parentOfV:
                #union
                parent[parentOfV]=parentOfU
                print(parent)
            else:
                return [u,v]
        return [] #若皆安全
    def find(self,node,parent):
        if parent[node]==node: #parent為自己 代表只有自己一點 返回自己即可
            return node
        else:
            root=self.find(parent[node],parent)
            return root

#測試用
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
result=Solution()
ans=result.findRedundantConnection(edges)
print(ans)
```

## C++:
``` cpp=
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        for (int i=1; i<=n; i++) parent[i]=i;
        //visit edges
        for (const auto& curEdge: edges){
            int u=curEdge[0], v=curEdge[1];
            int parentOfU=find(u, parent);
            int parentOfV=find(v, parent);
            //union
            if (parentOfU!=parentOfV)
                parent[parentOfV]=parentOfU;
            else
                return {u, v};
        }
        return {};
    }
    int find(int node, unordered_map<int, int>& parent){
        if (parent[node]==node)
            return node;
        else
            return find(parent[node], parent);
    }

private:
    unordered_map<int, int> parent;
};
```