786. Cut Vertices
A city's power grid has n substations numbered 0 to n - 1 and two-way lines in edges, where each [a, b] links substations a and b. A pair of substations may be linked by several lines, and the grid may consist of several unconnected regions.
A substation is critical if shutting it down (together with every line attached to it) increases the number of connected regions of the grid, that is, it breaks apart a region into two or more pieces. Return the numbers of all critical substations as a list sorted in ascending order, or an empty list if there are none. A substation with no lines is never critical.
Example 1
- Input:
- n = 7edges = [[0,1],[1,2],[2,3],[3,1],[3,4],[4,5],[5,6]]
- Output:
- [1,3,4,5]
- Explanation:
Substations 1 and 3 hold the pendant 0 and the tail to the triangle, and 4 and 5 sit in the middle of the tail 3-4-5-6; shutting any of them splits the grid, but 0, 2 and 6 do not. The answer is [1, 3, 4, 5].
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
- Output:
- []
- Explanation:
The four substations form a ring, so shutting any single one leaves the other three still connected: the answer is empty.
Example 3
- Input:
- n = 6, edges = [[0,1],[0,2],[0,3],[4,5]]
- Output:
- [0]
- Explanation:
Substation 0 is the hub of a star: without it 1, 2 and 3 are isolated from each other. The separate pair 4-5 has no critical substation, so the answer is [0].
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
- 0 ≤ a, b < n and a ≠ b
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 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)