Graphs Union-find
462. Redundant Connection
A tree is a connected graph with no cycle. You are given a graph that started as a tree on n nodes,
numbered from 1 to n, and then got one more edge. The new edge joins two different nodes that had no
edge between them.
The graph is given as edges, which has n rows. Each row [a, b] is an edge between nodes a and b,
and an edge works both ways.
Return an edge whose removal leaves a tree on all n nodes. If several edges would do, return the one that
comes last in edges, written exactly as it is there.
Example 1
Input: edges = [[2, 5], [1, 2], [3, 5], [2, 3], [4, 3]]
[2,3]Explanation: Nodes 2, 5 and 3 form a cycle through the edges [2,5], [3,5] and [2,3]. Removing any one of them
leaves a tree, and [2,3] comes last of the three.
Example 2
Input: edges = [[1, 4],
[4, 2],
[2, 3],
[3, 1],
[3, 5],
[5, 6]]
[3,1]Explanation: The cycle is 1, 4, 2, 3 and back to 1, and [3,1] is its last edge. The edges [3,5] and [5,6] come
later, but removing either one would cut nodes off.
Example 3
Input: edges = [[2, 3], [1, 3], [1, 2]]
[1,2]Explanation: All three edges form the cycle, so the answer is the last one.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
3 ≤ n ≤ 105, where n isedges.lengthedges[i].length == 21 ≤ ai, bi ≤ nandai ≠ bi- No two edges join the same pair of nodes.
- The graph is connected.
Clarifying questions
What you would ask an interviewer before writing any code.