Any one has solved this problem :
Given a undirected graph and two vertices : the source and the destination. What is the minimum number of vertices that need to be eliminated so that there is no path from the source to the destination ?
i am thinking but couldn't find a solution.
Moreover, i am finding a buddy who is interested in programming contest so that we can do and discuss programming contests together (any contests from uva.es to zju.edu.cn or from BOI to CEOI). I am international freshman studying in Computer Science in Canada.
My id is nooneknowsall@hotmail.com for MSN messenger.
Nice to meet every body from this forum.
Which vertices ?
Moderator: Board moderators
-
Whinii F.
- Experienced poster
- Posts: 151
- Joined: Wed Aug 21, 2002 12:07 am
- Location: Seoul, Korea
- Contact:
Maybe you could apply network flow to this problem. 
Build a network by setting every edge's capacity in the original graph to INFINITE.
Then divide all vertices (except the source and the destination) into two vertices. One named 'head' having only incoming edges, and one named 'tail' having only outgoing edges. And connect each pair of them with an edge with capacity 1. (Head -> Tail has capacity 1, but Tail -> Head should have capacity 0)
Then when you apply network flow to it, you will know how many vertices are there to be eliminated.
Doesn't it seem feasible?
Maybe you could look at problem 563, crimewave, which uses the similar idea. That might help..
Build a network by setting every edge's capacity in the original graph to INFINITE.
Then divide all vertices (except the source and the destination) into two vertices. One named 'head' having only incoming edges, and one named 'tail' having only outgoing edges. And connect each pair of them with an edge with capacity 1. (Head -> Tail has capacity 1, but Tail -> Head should have capacity 0)
Then when you apply network flow to it, you will know how many vertices are there to be eliminated.
Doesn't it seem feasible?
Maybe you could look at problem 563, crimewave, which uses the similar idea. That might help..
JongMan @ Yonsei