编程介的小学生 2019-09-21 21:44 采纳率: 20.5%
浏览 51

Water channels 的算法的问题

Problem Description
So many towns are in drought! The mayor is anxious!
Luckily, There is a reservoir on the mountain top, and the mayor wants to use the water there to irrigate the farmland. The only way is to build some NEW channels to connect the towns that in drought to the reservoir directly or indirectly. Now the problem is the mayor wants to konw what is the least number of channels that have to build to connect all the towns in drought to the reservoir directly or indirectly.

Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n(0 <= n <= 100), following n pairs of towns in the form "A B", means there has been a channel from A to B. The third line contains a positive integer m(0 <= m <= 16), following m lines containing the names of those towns in drought. The last line contains a town's name which the reservoir is in. You should note that the names of the towns only contain 'A' to 'Z',and their length will less than 100.

Output
For each test case, output one line containing the minimum number of channels you have to built.

Sample Input
2
A B
B C
2
B
C
A
1
A B
2
B
C
A

Sample Output
0
1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题