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


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

* Use Union Find: time O(n)
* 字典紀錄每個節點與其對應的parent
* key為該node
* value為該node的parent
* 初始: parent皆為node自己

        parent=defaultdict(int)
        for i in range(1,len(edges)+1):
            parent[i]=i 

* 逐一遍歷所有邊

        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:

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++:

#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;
};