编程介的小学生 2018-12-24 20:34 采纳率: 20.5%
浏览 358
已采纳

两个图的比较问题,怎么计算出这里车站的编号,用C语言

Problem Description
jiefangxuanyan and yiyi cat are universally acknowledged model couples. Once jiefangxuanyan has time, he takes a train to yiyi cat’s city and meet her. This time, as usual, jiefangxuanyan gets out from the railway station, and enters the subway, only to find that the subway stations of the whole city changes their names!

As a direction idiot, jiefangxuanyan felt helpless with this situation. He called yiyi cat for help. Because the subway map is so complicated, she can’t remember it either. Fortunately, only the names of the stations changed, the structure of subway lines is the same. So she picks out the old map to make a mapping.

But mapping such a confused subway map is definitely a difficult task. So she has to use the computer. Unfortunately, she just spilt wonton soup into her computer. So, yiyi cat asked you for help, hoping you can help her with this problem.

The subway in the city forms a tree, with N subway stations and N-1 subway lines. Any pair of stations are connected with one or more subway lines. You need to find a bijective mapping from the old names to the new names, that for each pair of stations connected by exactly one line in the old map, their new names are also connected by exactly one line in the new map.

Input
The input has multiple test cases, please process to the end of file.

For each test case, the first line is an integer N(1≤N≤100000).

In the following N−1 lines, each line has two space-separated string, as two stations connected by one line in the old map.

In the following N−1 lines, each line has two space-separated string, as two stations connected by one line in the new map.

Station names are no longer than 10 characters, and only consists of lowercase letters (a~z).

Output
For each test case, output N lines.

Each line consists two space-separated string, as the old name and its corresponding new name.

Both the names appeared in the old and new subway map should appear exactly once in the output.

You can output the names in any order. And if there are multiple valid mappings, output any one.

Names in the old map and the new map may be the same, but this does not mean these two stations are the same.

Sample Input
3
a b
b c
b a
a c

Sample Output
b a
a b
c c

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-08-28 22:25
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

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