psywoo's blog

How to solve this easy looking Graph problem ?
By psywoo, history, 3 years ago, In English

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 :)

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

never mind, just realized it would not work.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you exactly choose the node for which all weights across it are equal to 1?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

does this code work? CODE

→ Reply