1
class UnionFind:
2

3
    def __init__(self, size):
4

5
        self.parent = [-1 for _ in range(size)]
6
        self.rank = [-1 for _ in range(size)]
7

8
    def find(self, i):
9

10
        if self.parent[i] == -1:
11
            return i
12

13
        k = self.find(self.parent[i])
14
        self.parent[i] = k
15
        return k
16

17
    def union(self, x, y):
18

19
        x = self.find(x)
20
        y = self.find(y)
21

22
        if x == y:
23
            return -1
24
        else:
25

26
            if self.rank[x] > self.rank[y]:
27
                self.parent[y] = x
28

29
            elif self.rank[x] < self.rank[y]:
30
                self.parent[x] = y
31

32
            else:
33
                self.rank[x] += 1
34
                self.parent[y] = x
35

36

37
class Solution:
38
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
39

40
        vertex_set = set()
41

42
        for edge in edges:
43
            vertex_set.add(edge[0])
44
            vertex_set.add(edge[1])
45

46
        union_find = UnionFind(len(vertex_set))
47

48
        for edge in edges:
49

50
            new_edge = [edge[0] - 1, edge[1] - 1]
51

52
            if union_find.union(new_edge[0], new_edge[1]) == -1:
53
                return edge
54

55
        return []