"""

simple union find with path compression:

at first, each vertices are disjoint, there are N connected components at the begining,

after add each edge, we unify those two connected components, if two vertices are already

in the same connected component, then this edge will form a circle, just return this edge

"""

def findRedundantConnection(self, edges):

id = list(range(len(edges) + 1))

def find(u):

root = u

while root != id[root]: root = id[root]

while u != root:

next = id[u]

id[u] = root

u = next

return root

for u, v in edges:

root1, root2 = find(u), find(v)

if root1 == root2: return [u, v]

id[root1] = root2