最近公共祖先·一
Time Limit: 1 Sec Memory Limit: 256 MB
小Ho最近发现了一个神奇的网站!

传送门:HIHO1062

Input

每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。 每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。 每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。 对于100%的数据,满足N<=10^2,M<=10^2, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人)。

Output

对于每组测试数据,对于每个小Hi的询问,输出一行,表示查询的结果:如果根据已知信息,可以判定询问中的两个人存在共同的祖先,则输出他们的所有共同祖先中辈分最低的一个人的名字,否则输出-1。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu

Sample Output

1
2
3
JiaDaishan
JiaZheng
-1

题解

这个数量级暴力就行了 通过map存父子关系 然后用一个set保存查询第一个所有父节点(包括自己) 然后遍历一遍第二个的父节点(包括自己)是否存在在set中 越前面表示越近
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.io.*;  
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int count=0;
HashMap<String,String>map=new HashMap<String,String>(); //map存关系
for(int i=1;i<=n;i++){
String parent=sc.next();
String son=sc.next();
if(!map.containsKey(son))map.put(son,parent);
}
int m=sc.nextInt();
for(int i=1;i<=m;i++){
String s1=sc.next();
String s2=sc.next();
HashSet<String>set=new HashSet<String>(); //存第一个的父节点,包括自己
set.add(s2);
while(map.containsKey(s2)){
set.add(map.get(s2));
s2=map.get(s2);
}
String result=null;
if(set.contains(s1)){
result=s1;
}else{
while(map.containsKey(s1)){
if(set.contains(map.get(s1))) {
result=map.get(s1);
break;
}
s1=map.get(s1);
}
}
if(result==null) System.out.println(-1);
else System.out.println(result);
}
}
}
}