PreviousNext
Coding/Graphs and trees

Minimum edge cut

Write codeHard40 min

Your task

Given an undirected graph with n nodes (0..n-1) and edges [u, v] (each edge has unit strength), find the minimum number of edges whose removal disconnects a given source node from a given sink node. If they are already disconnected, return 0. Parallel edges count separately. Constraints: 1 <= n <= 200.

Examples

min_edge_cut(n: int, edges: list[list[int]], source: int, sink: int) -> int
Example 1
Inputmin_edge_cut(3, [[0, 1], [1, 2]], 0, 2)
Output1