Hello kids,
I am having a bit trouble with this problem from the IOI 1995. I solved part (1) by removing each node and checking for connectivity, but I cannot know how to solve part two, or give some reformulating in terms of graph theory. I cannot really understand what this part B is saying or asking for. (Some simple condition like part (1))
Does anyone have any ideas?
Thanks very much!
From my understanding, you have to report all v such that you can partition all the arrows into two vertex-disjoint* sets P and Q, such that s is in P and t in Q. And P and Q are valid courses according to the 3 properties mentioned in the statement. P is a s - v course and Q is a v - t course.
*: except v, which belongs to both sets.
This task is rather old (1995) and hence the constraints are very low. I couldn't find an online judge for it, but this year's IOI practice task "Graph" was basically task 1 with today's constraints. You can find its statement here: http://ioi2015.kz/content/view/1/270. Check it out.
Part 2, the splitting points, is the same as finding articulation points in an undirected graph. For this part, treat the graph edges as undirected, because we're interested in connectivity between the 2 parts.
There is a lot of information about articulation points on the web, e.g.
https://en.wikipedia.org/wiki/Biconnected_component
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
I do'd exactly this. For part A, it is similar problems, yes sir, but graph is become directed. But what happen? I got the WA, verdict, for the part B on test 3.
Can you look it?
Thank!
There is a tricky point: the splitting point can not have outgoing edges to both parts (otherwise these parts share edges).