题目链接：http://hihocoder.com/problemset/problem/1062
题意裸，有个trick，导致我当年做的时候一直在WA...
那就是出现这种没有出现在关系中，但是依然可以知道他们关系的输入样例： LinDaiyu LinDaiyu
应该输出自己。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 2021; 5 int n, m, q; 6 map<string, int> id; 7 string di[maxn]; 8 vector<int> G[maxn]; 9 int depth[maxn], fa[maxn], in[maxn]; 10 char a[maxn], b[maxn]; 11 int pre[maxn]; 12 13 int find(int x) { 14 return x == pre[x] ? x : pre[x] = find(pre[x]); 15 } 16 17 void unite(int x, int y) { 18 x = find(x); 19 y = find(y); 20 if(x != y) pre[x] = y; 21 } 22 23 void dfs(int u, int p, int d) { 24 depth[u] = d; 25 fa[u] = p; 26 for(int i = 0; i < G[u].size(); i++) { 27 int &v = G[u][i]; 28 if(v == u || v == p) continue; 29 dfs(v, u, d+1); 30 } 31 } 32 33 int query(int u, int v) { 34 if(find(u) != find(v)) return -1; 35 if(depth[u] < depth[v]) swap(u, v); 36 while(depth[u] > depth[v]) u = fa[u]; 37 while(u != v) { 38 u = fa[u]; 39 v = fa[v]; 40 } 41 return u; 42 } 43 44 int main() { 45 // freopen("in", "r", stdin); 46 while(~scanf("%d", &n)) { 47 id.clear(); m = 0; 48 memset(depth, 0, sizeof(depth)); 49 memset(in, 0, sizeof(in)); 50 for(int i = 0; i < maxn; i++) { 51 pre[i] = i; 52 G[i].clear(); 53 } 54 for(int i = 0; i < n; i++) { 55 scanf("%s %s", a, b); 56 if(id.find(a) == id.end()) { 57 id[a] = ++m; 58 di[m] = a; 59 } 60 if(id.find(b) == id.end()) { 61 id[b] = ++m; 62 di[m] = b; 63 } 64 G[id[a]].push_back(id[b]); 65 unite(id[a], id[b]); 66 in[id[b]]++; 67 } 68 for(int i = 1; i <= m; i++) { 69 if(!in[i]) { 70 dfs(i, -1, 1); 71 } 72 } 73 scanf("%d", &q); 74 while(q--) { 75 scanf("%s %s", a, b); 76 if(strcmp(a, b) == 0) { 77 puts(a); 78 continue; 79 } 80 if(id.find(a) == id.end() || id.find(b) == id.end()) { 81 puts("-1"); 82 continue; 83 } 84 int ret = query(id[a], id[b]); 85 if(ret == -1) puts("-1"); 86 else puts(di[ret].c_str()); 87 } 88 } 89 return 0; 90 }