2001 Canadian Computing Competition, Stage 1

Problem J5/S3: Strategic Bombing

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.

Input

In the input, each point is identified by a single upper-case letter (there are a maximum of 26 points). Each line of input identifies a pair of points connected by a road.

The end of input is indicated by a line containing "**". 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.

Output

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 that "There are n disconnecting roads.", where n is the number of such roads.

If there is no such road, output "There are 0 disconnecting roads."

Sample Input

AC
AD
AE
CE
CF
ED
GF
BG
HB
GH
**

Sample Output

CF
GF
There are 2 disconnecting roads.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Made for brute :D

Made for noobs

Read the "Rules on asking questions" comment on the main comments page, please.

Why is it only 2? Can't AC and BG be blown up as well?

If you blow up AC, you can still get from A to B:

A->E->C->F->G->B

do the roads need to be outputted in the order that they were inputted?

Does the problem [i]say[/i] they need to be outputted in any specific order?

(the answer is "no")

and the other half have 7, like ross and toby

CCC01J5S3 - Strategic Bombing (30 / 30) <-- Toby 

Ross has 7 because he did it before the CCC 30 pointer thing was started. You don't get more. 

Chris is the new care bear =) I kid I kid. 

but if the problem didnt get any harder, the why doesnt ross get his 23 points

the 30 pt deal doesn't apply to problems that you've fully solved already.

well it should