779. Extra Directed Cable
A company has n employees numbered 1 to n. Originally its reporting lines formed a rooted tree: one boss had no manager, every other employee had exactly one manager, and everybody reported to the boss directly or indirectly. Then one extra reporting line was added between two different employees. The list edges holds all n lines; [a, b] means that a is a manager of b (directed from a to b), and no line appears twice.
Return one line whose removal makes the remaining n - 1 lines a rooted tree again, written exactly as in edges. If several lines work, return the one that appears last in edges.
Example 1
- Input:
- edges = [[3,1],[1,2],[3,4],[2,5],[4,5]]
- Output:
- [4,5]
- Explanation:
Employee 5 has two managers, 4 and 2. Removing either
[2, 5]or[4, 5]leaves a rooted tree with boss 3, so the later-listed[4, 5]is returned.
Example 2
- Input:
- edges = [[5,4],[1,3],[3,5],[5,1],[1,2]]
- Output:
- [5,1]
- Explanation:
The lines 1->3, 3->5, 5->1 form a loop and every employee has exactly one manager. Removing any one of the three loop lines works; the last of them in the list is
[5, 1]. Removing[1, 2]or[5, 4]would leave the loop.
Example 3
- Input:
- edges = [[2,5],[4,1],[1,3],[2,1],[3,4]]
- Output:
- [4,1]
- Explanation:
Employee 1 has two managers (4 and 2) and 1->3->4->1 is a loop. Removing
[2, 1]would leave the loop with no boss, so the line to remove is[4, 1].
Constraints
- 3 ≤ n = edges.length ≤ 105
- edges[i] = [a, b] with 1 ≤ a, b ≤ n and a ≠ b
- Without one of the lines the graph is a rooted tree; no line is listed twice
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n * alpha(n))
- Space
- O(n)