LCA离线hiho1067

dfs(u)//marge和find为并查集合并函数和查找函数 { for each(u,v) //访问所有u子节点v { dfs(v); //继续往下遍历 marge(u,v); //合并v到u上 标记v被访问过; } for each(u,e) //访问所有和u有询问关系的e { 如果e被访问过; u,e的最近公共祖先为find(e); } } #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <iostream> #define INF 0x3f3f3f3f using namespace std; const int N=100005; map<string,int> q; vector<int> edge[N],que[N],num[N]; string nam[N]; int vis[N]= {0},in[N]= {0},f[N],ans[N]= {0}; int _find(int x) { if(f[x]!=x) return f[x]=_find(f[x]); return f[x]; } void dfs(int u) { f[u]=u; int up=edge[u].size(); for(int i=0; i<up; i++) { dfs(edge[u][i]); f[edge[u][i]]=u; } vis[u]=1; up=que[u].size(); for(int i=0; i<up; i++) if(vis[que[u][i]]) ans[num[u][i]]=_find(que[u][i]); } int main() { int n,cnt=0; scanf("%d",&n); char s[25],ss[25]; for(int i=0; i<n; i++) { scanf("%s%s",s,ss); if(!q[s])q[s]=++cnt,nam[cnt]=s; if(!q[ss])q[ss]=++cnt,nam[cnt]=ss; int id1=q[s],id2=q[ss]; in[id2]++,edge[id1].push_back(id2); } scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s%s",s,ss); int id1=q[s],id2=q[ss]; que[id1].push_back(id2); que[id2].push_back(id1); num[id1].push_back(i); num[id2].push_back(i); } for(int i=1; i<=cnt; i++) if(in[i]==0) dfs(i); for(int i=0;i<n;i++) cout<<nam[ans[i]]<<endl; }