TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- This is a cycle prevention algorithm.
- Using Union Find, if a node and the node to connect to have the same root parent, then you are connecting an extra edge, and that extra edge must cause a cycle.
- By nature of Union Find, in the initialization step, all nodes are connected to each other via a self loop.
- Therefore, the only way two nodes have the same root parent is if those two nodes were joined together through some other edge (since there are no repeating edges).
- So, your node u connects to another node v, in which both u and v were previously connected to w (the root parent), which guarantees a cycle.
Complexity
Runtime
Space
Code
With Ranking
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# Labelled from 1 to n
parent = [i for i in range(len(edges) + 1)]
rank = [1] * (len(edges) + 1)
def union(x, y):
p1, p2 = find(x), find(y)
if p1 == p2:
return False
if rank[p1] > rank[p2]:
parent[p2] = p1
rank[p1] += rank[p2] # Consume p2's rank
else:
parent[p1] = p2
rank[p2] += rank[p1]
return True
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for x, y in edges:
# If x and y already had the same root parent, then connecting x to y again must cause a cycle
if not union(x, y):
return [x, y]With Path Compression
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# Labelled from 1 to n
parent = [i for i in range(len(edges) + 1)]
def union(x, y):
if find(x) == find(y):
return False
parent[find(x)] = y
return True
def find(x):
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for x, y in edges:
# If x and y already had the same root parent, then connecting x to y again must cause a cycle
if not union(x, y):
return [x, y]Union Find
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# Labelled from 1 to n
parent = [i for i in range(len(edges) + 1)]
def union(x, y):
if find(x) == find(y):
return False
parent[find(x)] = y
return True
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
return x
for x, y in edges:
# If x and y already had the same root parent, then connecting x to y again must cause a cycle
if not union(x, y):
return [x, y]DFS
Todo
DFS solution also possible, but slower.
Notes
Cards
START Basic Front: Redundant Connection Back: Use Union Find such that if a node had a root parent the same as the root parent of the node it is connecting to, then this forces a cycle.
DELETE END