'''
Description: 
Autor: Au3C2
Date: 2021-01-13 14:45:17
LastEditors: Au3C2
LastEditTime: 2021-01-13 14:46:43
'''
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        nodesCount = len(edges)
        parent = list(range(nodesCount + 1))

        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        for node1, node2 in edges:
            if find(node1) != find(node2):
                union(node1, node2)
            else:
                return [node1, node2]
        
        return []

# 树，中等，每日一题
# https://leetcode-cn.com/problems/redundant-connection/