Weak points of the network

A railway has n stations and two-way lines between them. A line is a bridge if closing it leaves the network in more separate parts than before. A station is a cut station (an articulation point) if closing it, with all its lines, leaves the stations that remain in more separate parts than before. Return a pair (bridges, cuts): the positions in lines of the bridges, and the cut stations, both in increasing order.

lines = [(0, 1), (0, 2), (1, 2), (2, 3),
         (3, 4), (3, 5), (4, 5), (4, 6)]
weak_points(7, lines)      # ([3, 7], [2, 3, 4])
weak_points(7, lines + [(3, 2)])   # ([7], [2, 3, 4])

This is lesson 3’s figure, with A to G as 0 to 6. The network may already be in several parts. Two lines may join the same two stations (then neither of them is a bridge), and a line may join a station to itself (it is never a bridge).

Limits

• Up to 100,000 stations and about 120,000 lines.
• The search can go 100,000 levels deep, so recursion is too deep. Closing each line in turn and counting parts again is too slow. The big tests have 4 seconds each.