Given an directed graph and two vertices u and v, remove minimum number of vertices such that v becomes unreachable from u. How to approach this problem?
Note: This question was asked in Juspay Hiring challenge on Hackerearth and contest has been ended.
Hey @galencolin, can you help me out??
What are the constraints? Looks like min cut. You can model the graph as one you can run maxflow on by splitting each vertex v into two vertices: in_v and out_v. All edges that previously went into v will instead go to in_v and edges that previous went out of v now go out of out_v, and all original edges have infinite capacity. Then, create an edge between each in_v and out_v with capacity 1, then run maxflow and you’ll have your answer.
There were no constraints… Will have to learn min-cut max flow algorithm.
Thank you for answering!!
Jeez… what kind of problem would require a possibly O(n^3) runtime (with ford-fulkerson) and not give constraints?
Problem was badly framed, I even sent a mail to setter at Hackerearth but no replies! Even the sample test case was too confusing… but still I solved the test-cases which had only 1 path between them.
Anyway thanks for taking your time & helping me out!