How to solve this easy looking Graph problem ?

Revision en1, by psywoo, 2022-05-18 05:36:18

Problem Statement :

You are given a Directed graph with N Vertices and M edges(it may or may not have cycles, it doesn't have multiple edges or self loops) and two vertices Start and End. You need to find the minimum number of vertices you need to block so that there is no way to reach Vertex End from the vertex Start. You cannot block the Start and End vertex.

Constraints :

4 <= N <= 1e5

3 <= M <= min(2e5 , N * (N — 1))

1 <= Start, End <= N

PS : Problem Source not known, But its Definitely not from a live contest :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English psywoo 2022-05-18 05:36:18 629 Initial revision (published)