題目鏈接：http://hihocoder.com/PRoblemset/problem/1067
【思路分析】離線算法是把所有的詢問先存儲起來，然后在深搜的過程中計算結(jié)果。本題本來就是一棵有根樹，應(yīng)該先計算根節(jié)點是多少，然后再從根節(jié)點進行深搜。實現(xiàn)為+深搜+并查集。 【AC代碼】
#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<map>#include<vector>using namespace std;#define N 100005int n,m;vector<int>G[N];map<string,int>num;vector<pair<int, int> >indexQuery[N];int result[N];int pre[N];string Name[N];int fin(int x){ if(pre[x]==x) { return x; } else { return pre[x]=fin(pre[x]); }}int fin1(int x){ if(pre[x]==-1) { return x; } else { return pre[x]=fin(pre[x]); }}void lca(int u){ pre[u]=u; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; lca(v); pre[v]=u; } for(int j=0;j<indexQuery[u].size();j++) { pair<int, int> p=indexQuery[u][j]; if(pre[p.first]!=-1) { result[p.second]=fin(p.first); } }}int main(){ while(~scanf("%d",&n)) { num.clear(); int cnt=0; //memset(pre,-1,sizeof(pre)); for(int i=0;i<N;i++)pre[i]=-1; for(int i=0;i<n;i++) { string str1,str2; cin>>str1>>str2; if(num.count(str1)==0) { num[str1]=cnt; Name[cnt]=str1; cnt++; } if(num.count(str2)==0) { num[str2]=cnt; Name[cnt]=str2; cnt++; } G[num[str1]].push_back(num[str2]); pre[num[str2]]=num[str1]; } scanf("%d",&m); for(int i=0;i<m;i++) { string str1,str2; cin>>str1>>str2; int num1=num[str1]; int num2=num[str2]; indexQuery[num1].push_back(make_pair(num2, i)); indexQuery[num2].push_back(make_pair(num1, i)); } int root=fin1(0); for(int i=0;i<N;i++)pre[i]=-1; lca(root); for(int i=0;i<m;i++) { cout<<Name[result[i]]<<endl; } } return 0;}新聞熱點
疑難解答
