# 0684. Redundant Connection

###### tags: `Leetcode` `Medium` `Graph` `DFS` `UnionFind`

---
用DFS的話就是找是不是會碰到走過的點相聯通，但看到檢查還想到並查集比較快

DFS

from collections import defaultdict
class Solution:
    def findRedundantConnection(self, edges):
        graph = defaultdict(list)
        
        
        def dfs(curr, goal):
            if curr == goal : return True
            visited.add(curr)
            if not graph[curr] or not graph[goal]: 
                return False
            for neighbor in graph[curr]:
                if neighbor in visited: continue
                if dfs(neighbor, goal):
                    return True
            return False
                
        for edge in edges:
            visited = set()
            if dfs(edge[0], edge[1]): 
                return edge
            
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            
        return None

併查集的話就是先擺好pose，然後初始化所有的根節點為自己，遍歷所有的邊，看看邊的兩端會不會有一樣的根節點，如果同一個根節點則返回這個邊，若不同則把兩個點合併

完全體併查集

class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n+1)]
        self.ranks = [1 for i in range(n+1)]
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, x, y):
        px, py = self.find(x), self.find(y) 
        if px == py:
            return False
        if self.ranks[px] < self.ranks[py]:
            self.p[px] = py
        elif self.ranks[px] > self.ranks[py]:
            self.p[py] = px
        else:
            self.p[px] = py
            self.ranks[px] += 1
        return True
        
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        s = UnionFind(len(edges))
        for i, j in edges:
            #根一樣代表是一圈
            if not s.union(i, j): 
                return [i, j]
        return None
         

簡化版併查集

class Solution:
    def findRedundantConnection(self, edges):
        self.p = [i for i in range(len(edges) + 1)]
        for i, j in edges:
            x = self.find(i)
            y = self.find(j)
            if x != y:
                self.p[x] = y
            else:
                return [i,j]
            
    def find(self, x):
        while self.p[x] != x:   
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x