Loading environment...
Problem Description
The Enemy relies heavily on the transportation of supplies and personnel between the specific points A and B. Points A and B, as well as other points C, D, E, etc., are linked by a network of roads. Your mission, should you accept it, is to identify a single road that may be bombed in order to cut off all traffic between A and B.
All roads are two-way, that is, road AC is the same as road CA. There is at most one road between any pair of points.
Input Specification
In the input, each point is identified by a single upper-case letter (there is a maximum of 26). Each line of input identifies a pair of points connected by a road. The end of input is indicated by a line containing **.
Output Specification
Your output should identify all roads such that bombing any one of them would halt all traffic between A and B. Your output should list the roads, one per line, followed by a line stating There are n disconnecting roads., where is the number of such roads. If there is no such road, output There are 0 disconnecting roads..
Sample Input
Output for Sample Input
Explanation of Output for Sample Input
Traffic flowing from point A to point B must pass through the roads CF and GF. For example, A can reach C directly or through E or D. From C, the only way to progress towards B is through point F, making the CF road critical. Similarly, from F, the only way to reach the cluster of nodes connected to B (which are G and H) is through the GF road. Therefore, bombing either CF or GF will completely disconnect A from B.
No comments yet. Be the first to comment!