Redundant Connection
- 1 min read
- Graph
- LC-Medium
3 years ago
Solution
- Use Union Find
- Go through edges, keep unioning them
- At any point, before unioning two edges, if they have the same parent, it means we've found a node that would create a cycle
| Time | Space | Explanation |
|---|---|---|
O(e + v) | O(v) |
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
rank = {i: 1 for i in range(1, n + 1)}
par = {i: i for i in range(1, n + 1)}
def find(a):
a = par[a]
while a != par[a]:
a = par[a]
return a
def union(a, b):
p1, p2 = find(a), find(b)
if p1 == p2:
return False
if rank[p1] > rank[p2]:
rank[p1] += rank[p2]
par[p2] = p1
else:
rank[p2] += rank[p1]
par[p1] = p2
return True
for a, b in edges:
if not union(a, b):
return [a, b]