题目链接：http://hihocoder.com/problemset/problem/1062
题意裸，有个trick，导致我当年做的时候一直在WA...
那就是出现这种没有出现在关系中，但是依然可以知道他们关系的输入样例： LinDaiyu LinDaiyu
应该输出自己。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int n, m, q;
map<string, int> id;
string di[maxn];
vector<int> G[maxn];
int depth[maxn], fa[maxn], in[maxn];
char a[maxn], b[maxn];
int pre[maxn]; int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x);
y = find(y);
if(x != y) pre[x] = y;
} void dfs(int u, int p, int d) {
depth[u] = d;
fa[u] = p;
for(int i = ; i < G[u].size(); i++) {
int &v = G[u][i];
if(v == u || v == p) continue;
dfs(v, u, d+);
}
} int query(int u, int v) {
if(find(u) != find(v)) return -;
if(depth[u] < depth[v]) swap(u, v);
while(depth[u] > depth[v]) u = fa[u];
while(u != v) {
u = fa[u];
v = fa[v];
}
return u;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
id.clear(); m = ;
memset(depth, , sizeof(depth));
memset(in, , sizeof(in));
for(int i = ; i < maxn; i++) {
pre[i] = i;
G[i].clear();
}
for(int i = ; i < n; i++) {
scanf("%s %s", a, b);
if(id.find(a) == id.end()) {
id[a] = ++m;
di[m] = a;
}
if(id.find(b) == id.end()) {
id[b] = ++m;
di[m] = b;
}
G[id[a]].push_back(id[b]);
unite(id[a], id[b]);
in[id[b]]++;
}
for(int i = ; i <= m; i++) {
if(!in[i]) {
dfs(i, -, );
}
}
scanf("%d", &q);
while(q--) {
scanf("%s %s", a, b);
if(strcmp(a, b) == ) {
puts(a);
continue;
}
if(id.find(a) == id.end() || id.find(b) == id.end()) {
puts("-1");
continue;
}
int ret = query(id[a], id[b]);
if(ret == -) puts("-1");
else puts(di[ret].c_str());
}
}
return ;
}