1077. Resilient Blocks
A telecom network has n stations numbered 0 to n-1 and bidirectional cables: edges[i] = [u, v] joins stations u and v. Several cables may join the same pair of stations. A cable from a station to itself carries no traffic and is ignored.
A resilient block is a largest possible group of cables with the following property: the stations touched by the group remain connected to each other, using only cables of the group, after any one of those stations is switched off. A single cable between two stations is a block by itself if nothing larger contains it. Every working cable belongs to exactly one block.
Return the number of resilient blocks in the network.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[2,0],[2,3],[3,4]]
- Output:
- 3
- Explanation:
The triangle 0-1-2 is one block, and the cables 2-3 and 3-4 are each a block of their own, giving 3.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
- Output:
- 1
- Explanation:
The four stations form one cycle; losing any one station leaves a path, so the whole network is a single block.
Example 3
- Input:
- n = 6, edges = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,2]]
- Output:
- 2
- Explanation:
Two triangles share station 2, which gives two blocks; station 5 has no cable and does not count.
Constraints
1 ≤ n ≤ 5 * 104
0 ≤ edges.length ≤ 105
edges[i].length == 2
0 ≤ edges[i][j] < n
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)