Remove the One Edge That Breaks a Rooted Hierarchy
A reporting hierarchy should be a rooted tree: one root with no manager, everyone else with exactly one manager, no cycles. Exactly one extra edge was added by mistake. Identify the edge to remove to restore a valid hierarchy.
Problem
A rooted tree on n nodes (1..n) had one extra directed edge added, producing edges (a list of n directed [parent, child] pairs). Return the edge that can be removed so the result is a rooted tree with exactly one root. If multiple answers exist, return the one that appears last in edges.
Input
A list edges of n directed [u, v] pairs.
Output
A single [u, v] edge to remove.
Constraints
- 3 <= n <= 1000
- edges.length == n
- Each edge is a directed pair; exactly one extra edge is present.
Examples
Example 1
Input
edges = [[1,2],[1,3],[2,3]]
Output
[2,3]
Node 3 has two parents; removing the later edge [2,3] fixes it.
Example 2
Input
edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output
[4,1]
No node has two parents, but there is a cycle; remove the cycle-closing edge.