Repair the Reporting Line
HardGraphs
Problem
A company's reporting structure was a rooted tree: one chief with no manager, and every other employee 0 to n - 1 with exactly one manager. Each entry [m, e] of links means m manages e. A data-entry error added one extra link between two different employees, so links now has n entries.
Return the link whose removal restores a valid rooted tree (one root, every other employee with exactly one manager, everyone reachable from the root). If several links qualify, return the one that appears last in links.
Example 1
- Input:
- links = [[0, 1], [0, 2], [1, 2]]
- Output:
- [1, 2]
Employee 2 has two managers; removing either link works, and [1, 2] comes last.
Example 2
- Input:
- links = [[0, 1], [1, 2], [2, 3], [3, 0], [0, 4]]
- Output:
- [3, 0]
Nobody has two managers, but 0 → 1 → 2 → 3 → 0 is a loop and there is no chief. Only loop links are removable, and [3, 0] is the last of them.
Example 3
- Input:
- links = [[1, 2], [2, 0], [0, 1], [3, 1]]
- Output:
- [0, 1]
Employee 1 has two managers and one of them, 0, is inside a loop. Removing [3, 1] would leave the loop, so [0, 1] must go.
Constraints
- 3 ≤ n = links.length ≤ 10^4
- 0 ≤ m, e < n, m ≠ e
- No link is listed twice.
- The input is a rooted tree plus exactly one extra link.
Hint
Show the first hint
Adding one directed link to a rooted tree can break it in two ways. What are they?
Walkthrough
How to approach it
01Clarify before coding
- Is the extra link always between two different employees? Yes, no self-links.
- Must the result keep everyone reachable from one root? Yes, it must be a valid rooted tree.
- What does 'last' mean when the loop has several links? The one with the largest index in links.
02Brute force
Try removing each link from last to first and check whether the remaining links form a rooted tree (one in-degree-0 node, all others in-degree 1, everything reachable).
Cost: O(n) candidates × O(n) per check = O(n²): 10^8 steps at n = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.