'''
keys: union find, the redundant edge will form a loop
Solutions:
Similar: 959
T:
S:
'''
from typing import List
import collections





# huahua version
class UnionFindSet:
    def __init__(self, n): # number of nodes, 1 plus number of edges
        self._parents = [i for i in range(n + 1)]
        self._ranks = [1 for i in range(n + 1)]
    
    def find(self, u): # find root, path compression
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u
    
    def union(self, u, v): # optimized by rank
        pu, pv = self.find(u), self.find(v)
        if pu == pv: return False # already in the same set
        
        if self._ranks[pu] < self._ranks[pv]:
            self._parents[pu] = pv
        elif self._ranks[pu] > self._ranks[pv]:
            self._parents[pv] = pu
        else: # break the tie randomly
            self._parents[pv] = pu
            self._ranks[pu] += 1 # the rank of the smaller one increases
        
        return True


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        s = UnionFindSet(len(edges)) # number of edges
        for edge in edges:
            if not s.union(edge[0], edge[1]): # alreay in the same set
                return edge
        return None



class Solution:

    # UF, T: O(nlogn) = O(n), 
    def findRedundantConnection1(self, edges: List[List[int]]) -> List[int]:
        parents = [0] * (len(edges)+1) # 0 means no parent
        sizes = [1] * (len(edges)+1) # size of node itself is 1
        
        for edge in edges:
            u = edge[0]; v = edge[1]
            if not parents[u]: parents[u] = u
            if not parents[v]: parents[v] = v
            pu = self.find(u, parents) # find root node of u
            pv = self.find(v, parents)
            
            if pu == pv: return edge # in the same tree
            # union, merge smaller set pv to the larger set pu
            # if pv > pu, make pv the smaller one
            if sizes[pv] > sizes[pu]:
                pv, pu = pu, pv
            
            parents[pv] = pu # pv's parent is pu
            sizes[pu] += sizes[pv]
        return {}
            
    def find(self, node, parents):
        # notice that here only one while loop instead of two
        while parents[node] != node: # node is not the root node now
            parents[node] = parents[parents[node]] # make grandpa as parent
            node = parents[node] # go to the parent node
        return node # if parents[node] == node

    
    # DFS, T: O(n^2)
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        for edge in edges:
            u = edge[0]
            v = edge[1]
            
            visited = set()
            if self.hasPath(u, v, graph, visited):
                # there is a path from u to v, adding the u-v edge will make
                # a loop, so that's the redundant one
                return edge 
            
            graph[u].append(v)
            graph[v].append(u)
        return {} # not found
        
    def hasPath(self, curr, goal, graph, visited):
        if curr == goal: return True
        visited.add(curr)
        if curr not in graph or goal not in graph:
            return False # u, v not in graph
        for nei in graph[curr]: # neighbors
            if nei in visited:
                continue
            if self.hasPath(nei, goal, graph, visited):
                return True
        return False
            
            