1737. The Longest Chain of Fragile Links

An UNDIRECTED graph has n vertices and m edges. Two vertices in the same connected piece are SEPARATED BY a given edge when deleting that one edge leaves no path between them.

For each pair of vertices in the same piece, count the edges that separate them. Print the largest count over all pairs, and 0 when no pair is separated by anything.

1-2, 2-3, 3-4 -> 3 vertices 1 and 4 1-2, 2-3, 3-1 -> 0 nothing separates anything 1-2, 2-3, 3-1, 3-4 -> 1 any of 1, 2, 3 against 4 1-2, 3-4 -> 1 the pairs across components do not count 1 vertex, no edges -> 0

Only edges that are BRIDGES can separate anything, since deleting a non-bridge leaves the graph connected. So this is the length of the longest chain of bridges a route has to cross.

## The three things that have to be said

directed? no. self-loops? allowed, never a bridge, never separates anything. parallel edges? allowed, never a bridge, never separates anything. disconnected? allowed, and a pair in two different pieces is not counted at all, which is why the fourth example answers 1 and not something larger.

## What most people try first

The definition: for every pair and every edge, delete the edge and test connectivity. That is O(n^2 m (n + m)), which is what this problem's oracle does on seven-vertex graphs and which is hopeless beyond that.

A better but still wrong idea is the DIAMETER of the graph, the largest shortest path. On a triangle with a long tail the diameter counts the tail plus a step inside the triangle, and the edge inside the triangle separates nothing. The third example above is the small version: the diameter from 1 to 4 is 2 and the answer is 1.

## Squeeze the bridgeless pieces to points

Problem 1735 shows that deleting every bridge leaves the TWO-EDGE-CONNECTED pieces. Contract each of those to a single point and keep the bridges as edges. What remains is a FOREST, called the bridge forest:

it has no cycle, because a cycle in it would mean a cycle in the original graph passing through bridges, and no edge of a cycle is ever a bridge

Two vertices of the original graph are separated by exactly the bridges on the unique path between their two points in that forest, since any route between them must use every bridge on that path and can avoid every other bridge. So the answer is the largest number of edges on a path of the forest, in other words its DIAMETER measured in edges.

## Labelling the pieces without a disjoint set

Walk the search's entry order forwards. A vertex is in the same piece as its parent exactly when the tree edge between them is not a bridge:

for v in entry order: if v is a root, or the edge pe[v] is a bridge: give v a new piece number else: piece[v] = piece[par[v]]

That is correct because a non-bridge tree edge survives the deletions, and a back edge never crosses between pieces: its tree path contains no bridge, since a bridge on that path would lie on a cycle.

## The diameter of a forest, in two searches per tree

from any vertex, breadth-first search and keep the furthest vertex a from a, breadth-first search again; the furthest distance is the diameter

Why that works on a tree: let the diameter run between x and y. From any start s, the furthest vertex found is an endpoint of some diameter. Suppose not, and let a be the furthest from s; take the point p where the path from s meets the path from x to y. Since a is at least as far from p as either x or y is, replacing an endpoint by a gives a path at least as long, so a is a diameter endpoint after all. Then the second search from a finds the full length.

Run this per tree of the forest and take the largest.

## Cost

Time O(n + m log m): one low-link search, one labelling sweep, and two breadth-first searches per tree over at most n points and m bridges. Space O(n + m). All searches are ITERATIVE, since a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

## Related

Problem 1735 counts the points of this forest. Problem 1738 asks how much damage one bridge does rather than how many of them stack up. Problem 391 finds the longest walk in a tree, which is the two-search trick on a tree given directly.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected