Single Points of Failure

MediumAdvanced Graphs

Problem

A power grid has n substations joined by undirected lines lines[i] = [u, v]. A substation is a single point of failure if taking it offline (together with all its lines) increases the number of disconnected groups among the remaining substations.

Return all single points of failure in ascending order.

Example 1

Input:
n = 5, lines = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output:
[1, 3]

Removing 1 cuts {3, 4} from {0, 2}; removing 3 isolates 4.

Example 2

Input:
n = 3, lines = [[0,1],[1,2],[2,0]]
Output:
[]

Example 3

Input:
n = 4, lines = [[0,1],[0,2],[0,3]]
Output:
[0]

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ lines.length ≤ 2·10^4
  • u ≠ v; no duplicate lines
  • The grid may already be disconnected.

Hint

Show the first hint

Removing each substation and re-running BFS works, but it is O(n·(n + E)).

Walkthrough

How to approach it

01Clarify before coding

  • Does removing a substation also remove its lines? Yes.
  • Is a leaf ever critical? No: removing it leaves the rest connected.
  • Is the grid connected? Not necessarily; each component is handled separately.

02Brute force

For each substation, delete it and count connected components with BFS, comparing to the original count.

Cost: O(n · (n + E)) ≈ 10^4 · 3·10^4 = 3·10^8: too slow.

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.

Solve it in the browserStart free

This problem is part of Pro.