Fortify the Network

HardAdvanced Graphs

Problem

A connected network of n routers is joined by undirected cables links[i] = [u, v]. Currently some cables are fragile: cutting one of them splits the network.

Return the minimum number of new cables that must be added (between any routers) so that afterwards no single cable failure can split the network.

Example 1

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

Adding a cable 4–0 puts the chain 1–3–4 on a cycle.

Example 2

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

Three leaves hang off router 0 and each needs a new cable end, so one cable is not enough; adding 1–2 and 2–3 puts every original cable on a cycle.

Example 3

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

Constraints

  • 1 ≤ n ≤ 10^4
  • n - 1 ≤ links.length ≤ 2·10^4
  • The network is connected; u ≠ v.

Hint

Show the first hint

Groups of routers that are already robust (no bridge inside) can be treated as single super-nodes.

Walkthrough

How to approach it

01Clarify before coding

  • Is the network connected? Yes.
  • Can new cables join any two routers, even ones already linked? Yes.
  • One router or an already robust network? Answer 0.

02Brute force

Try adding 1, 2, 3, … cables in every possible position and test for bridges each time.

Cost: C(n², k) placements for k cables, each followed by an O(n + E) check: exponential.

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.