PreviousNext
Coding/Graphs and trees

Maximum vertex-disjoint paths

Write codeHard50 min

Your task

Given a directed graph with n nodes (0..n-1) and edges [u, v], find the maximum number of internally vertex-disjoint paths from a given source to a given sink: paths that share no intermediate vertex (they may share only the source and sink). Return that count. Constraints: 1 <= n <= 100.

Examples

max_vertex_disjoint_paths(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputmax_vertex_disjoint_paths(4, [[0, 1], [1, 3], [0, 2], [2, 3]], 0, 3)
Output2