PreviousNext
Coding/Graphs and trees

Maximum edge-disjoint paths

Write codeMedium30 min

Your task

You are given a directed graph on n nodes (0..n-1) as edges [u, v], a source s, and a target t. Find the maximum number of edge-disjoint paths from s to t: paths that may share nodes but where no directed edge is used by more than one path. Return that maximum count (0 if t is unreachable or s == t). Constraints: up to 60 nodes; parallel edges allowed.

Examples

max_disjoint_paths(n: int, edges: list[list[int]], s: int, t: int) -> int
Example 1
Inputmax_disjoint_paths(4, [[0, 1], [0, 2], [1, 3], [2, 3]], 0, 3)
Output2