Global edge connectivity
Your task
Given a connected undirected graph with n nodes (0..n-1) and edges [u, v] (each edge has unit capacity; parallel edges increase capacity), return its global edge connectivity: the minimum number of edges whose removal disconnects the graph (equivalently the global minimum cut). For n <= 1 return 0. Use max-flow/min-cut: fix one node and take the min over all other nodes of the s-t max flow. Assume 1 <= n <= 60 so repeated unit-capacity max-flow finishes under 5s.
Examples
edge_connectivity(n: int, edges: list[list[int]]) -> intExample 1
Input
edge_connectivity(4, [[0, 1], [1, 2], [2, 3], [3, 0]])Output
2