Proficient Level
Implement the findRedundantConnection method that returns the edge that creates a cycle in an undirected graph.
You are given an undirected graph that started as a tree and then had one extra edge added. The edges are provided as pairs [u, v].
Return the edge that can be removed so the graph becomes a tree again. If multiple answers appear possible while scanning, return the first edge that creates a cycle in the given order.
Example 1
Input
edges (int[][]) =
[[1,2],[1,3],[2,3]]size (int) =
3Returns (int[])
[2,3]Example 2
Input
edges (int[][]) =
[[1,2],[2,3],[3,4],[1,4],[1,5]]size (int) =
5Returns (int[])
[1,4]Example 3
Input
edges (int[][]) =
[[1,2],[2,3],[1,3]]size (int) =
3Returns (int[])
[1,3]Use the Union-Find data structure.
For every edge, check whether both nodes already belong to the same connected component. If they do, adding that edge creates a cycle, so that edge is the answer. Otherwise, union the two components and continue.
Path compression and union by rank keep the operations efficient.
Pseudocode:
function findRedundantConnection(edges, size):
initialize parent for each node
for each edge [u, v] in edges:
rootU = find(u)
rootV = find(v)
if rootU == rootV:
return [u, v]
union(rootU, rootV)
return []Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run