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 :)
You think of mcmf to find the amount of chokepoints in the graph, this reminds me of something similar to https://www.spoj.com/problems/BANKROB/ But for those constraints I'm not really sure
never mind, just realized it would not work.
You can solve this with regular flow (no need for the slower mcmf as others have suggested). Your graph is just the input graph with edges set to infinity and nodes split, with the weight across one node being equal to 1. The min cut across this graph is what you're looking for. That's always equal to the max flow, which can be calculated with Dinic's algorithm.
How do you exactly choose the node for which all weights across it are equal to 1?
For every node except the start node, you split that node into two new nodes. The edge from the entrance to that node to the exit of that node will have weight 1.
does this code work? CODE