Minimum Cut

Find the minimum number of edges whose removal disconnects a connected undirected graph.

graphs max-flow min-cut bfs networkx

You are given a connected, undirected, unweighted graph with N vertices (numbered 0 to N-1) and M edges. The graph is represented as an adjacency list: a list of lists, where `adj[i]` contains all vertices adjacent to vertex i. Edges are undirected, so each undirected edge {u,v} appears in both `adj[u]` and `adj[v]`. There are no self-loops and no multi-edges.

Implement the function `minimum_cut(adj: list[list[int]]) -> int` that returns the minimum number of edges that must be removed to disconnect the graph into at least two non-empty components. That is, the size of the minimum edge cut.

The graph is guaranteed to be connected. The graph size is small enough that a simple repeated max-flow (e.g., Edmonds-Karp) will pass. You may choose any approach, but the algorithm must be correct for all test cases.

Return the integer minimum cut size.

Constraints

- 2 <= N <= 50
- 1 <= M <= 200 (connected guarantee, so M >= N-1)
- Graph is undirected, no self-loops, no multi-edges.
- Complexity: A straightforward O(N * (M^2)) per max-flow or O(N^3) per max-flow is acceptable. The tests are sized for Python to run in under a couple of seconds.

Example

>>> adj = [[1,2],[0,2],[0,1]]  # triangle graph
>>> minimum_cut(adj)
2
>>> adj = [[1],[0,2],[1]]  # path of 3 vertices
>>> minimum_cut(adj)
1

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the min-cut between a fixed source and all other sinks (or a fixed pair).

Try all possible source-sink pairs, compute the max flow for each, and take the minimum.

For max flow, implement a simple BFS-based Ford-Fulkerson (Edmonds-Karp).

Remember to convert undirected edges into two directed arcs with capacity 1 in each direction.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.