857. Guard the Corridors
A museum has n halls numbered 0 to n - 1, joined by n - 1 corridors so that exactly one route exists between any two halls. Each entry edges[i] = [a, b] is a corridor between halls a and b. A guard stationed in a hall watches every corridor that touches that hall.
Return the smallest number of guards that must be stationed so that every corridor is watched by a guard standing at one (or both) of its two ends. A museum with a single hall has no corridors, so the answer is 0.
Example 1
- Input:
- n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]
- Output:
- 2
- Explanation:
Guards in halls 1 and 3 watch all five corridors (0-1, 1-2, 1-3, 3-4, 3-5), and no single hall touches every corridor, so 2 guards are needed.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- 2
- Explanation:
The corridors form a line 0-1-2-3; guards in halls 1 and 2 cover all three corridors, while one guard cannot cover both end corridors.
Constraints
- 1 ≤ n ≤ 105
edges.length == n - 1, 0 ≤ a, b < n and the corridors form a tree
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 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)