Graph Theory37 sections · 1633 units
Open in Course

Problem - Distinct Routes - Read Statement

(CSES 1711)

Read the problem at https://cses.fi/problemset/task/1711. You have a directed graph with nn vertices and mm edges. Find the maximum number of edge-disjoint paths from vertex 11 to vertex nn. Two paths are edge-disjoint if they do not share any edges (they can share vertices). Output the number of such paths and list each path as a sequence of vertices.

This translates to max flow where each edge has capacity 11. The flow value is the number of disjoint paths. Then you decompose the flow to extract the actual paths.