Robust Network Zones

MediumAdvanced Graphs

Problem

A data centre has n servers linked by undirected cables links[i] = [u, v] (two servers may share several cables). A robust zone is a maximal group of servers that stay connected to each other even if any single cable fails.

Return the number of robust zones. A server with no redundant connection forms a zone on its own.

Example 1

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

Cables 1–3 and 3–4 are single points of failure. The zones are {0,1,2}, {3} and {4}.

Example 2

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

Example 3

Input:
n = 4, links = []
Output:
4

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ links.length ≤ 2·10^4
  • u ≠ v

Hint

Show the first hint

Which cables separate zones? Exactly the ones whose failure disconnects something.

Walkthrough

How to approach it

01Clarify before coding

  • Is a zone defined by cable failures or server failures? Cable failures (2-edge-connectivity).
  • Do parallel cables make a pair robust? Yes, either cable can fail.
  • Do isolated servers count? Yes, each is its own zone.

02Brute force

For each pair of servers, check whether removing any single cable disconnects them.

Cost: O(n² · E · (n + E)): far beyond limits.

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.