hihoCoder 1067 : 最近公共祖先·二（map+离线Tarjan算法）

2019-11-10 20:36:59

字体：大中小

来源：转载

供稿：网友

题目链接：http://hihocoder.com/PRoblemset/problem/1067

【思路分析】离线算法是把所有的询问先存储起来，然后在深搜的过程中计算结果。本题本来就是一棵有根树，应该先计算根节点是多少，然后再从根节点进行深搜。实现为+深搜+并查集。【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;}

上一篇：P1048 采药

下一篇：P1996 约瑟夫问题