LC 0684 [M] Redundant Connection - ALawliet/algorithms GitHub Wiki
path compression: https://www.youtube.com/watch?v=VHRhJWacxis&ab_channel=WilliamFiset
https://www.youtube.com/watch?v=FXWRE67PLL0&ab_channel=NeetCode
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# include 0 to make it easier but don't use it
par = [i for i in range(len(edges) + 1)]
rank = [1] * (len(edges) + 1)
def find(n):
p = par[n]
while p != par[p]: # self loop
prev = par[p]
par[p] = par[prev] # path compression
p = par[p] # next
return p
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2: # same parent is redundant
return False
if rank[p1] > rank[p2]:
par[p2] = p1
rank[p1] += rank[p2]
else:
par[p1] = p2
rank[p2] += rank[p1]
return True
for n1, n2 in edges:
if not union(n1, n2):
return [n1, n2]