Description
An undirected graph with labels 1..n was formed from a tree by adding one edge. Return the removable edge that appears last in the supplied edge order.
Solution
def find_redundant_connection(edges):
parent = list(range(len(edges) + 1))
size = [1] * len(parent)
def find(node):
while node != parent[node]:
parent[node] = parent[parent[node]]
node = parent[node]
return node
for a, b in edges:
a_root, b_root = find(a), find(b)
if a_root == b_root:
return [a, b]
if size[a_root] < size[b_root]:
a_root, b_root = b_root, a_root
parent[b_root] = a_root
size[a_root] += size[b_root]
return []Examples
Example 1
- Input
[[[1,2],[1,3],[2,3]]]- Output
[2,3]
The last edge closes a triangle.
Example 2
- Input
[[[1,2],[2,3],[3,4],[1,4],[1,5]]]- Output
[1,4]
1 and 4 are already connected when that edge arrives.
Example 3
- Input
[[[1,2],[2,3],[3,1]]]- Output
[3,1]
Return the edge with its supplied endpoint order.
Approach
Use disjoint sets. Process edges in input order: if their endpoints already share a representative, the edge closes the cycle and is the required answer. Otherwise merge their components using size and path compression.
Time & space
O(n alpha(n)) time and O(n) auxiliary space, where n is the node/edge count and alpha is the inverse Ackermann function.