hiho一下 第十五周 最近公共祖先·二 - 更新一下tarjan離線LCA模闆

                 題意:

                          裸LCA

                 題解:

                          tarjan離線解LCA模闆...

Program:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h> 
#include<string>
#include<queue>
#include<map>
#include<algorithm>
#define MAXN 100005
#define ll long long
#define oo 1e+10
#define eps 1e-10
using namespace std; 
struct node
{
      int u,v,id,next;
}edge[MAXN],Qedge[MAXN<<1];
map<string,int> H;
int En,Vn,_next[MAXN],D[MAXN],father[MAXN];
int Qen,Qnext[MAXN],ans[MAXN];
bool visited[MAXN];
char st[MAXN];
string s,name[MAXN];
int getdata()
{
      scanf("%s",st),s=st;
      if (H.find(s)==H.end()) H[s]=++Vn,name[Vn]=s;
      return H[s];
}
void addedgeE(int u,int v)
{
      edge[++En].next=_next[u],_next[u]=En;
      edge[En].v=v;
}
void addedgeQ(int u,int v,int id)
{
      Qedge[++Qen].next=Qnext[u],Qnext[u]=Qen;
      Qedge[Qen].v=v,Qedge[Qen].id=id;
}
int getfather(int u)
{
      if (father[u]==u) return u;
      return father[u]=getfather(father[u]);
}
void tarjan(int u)
{
      int k,v,id;
      father[u]=u;
      visited[u]=true;
      for (k=Qnext[u];k;k=Qedge[k].next)
      {
               v=Qedge[k].v,id=Qedge[k].id;
               if (!visited[v]) continue;
               ans[id]=getfather(v);
      }
      for (k=_next[u];k;k=edge[k].next)
      {
               v=edge[k].v; 
               tarjan(v);
               father[v]=u;
      }
}   
int main()
{       
      int n,Q,i,u,v;
      string s;  
      scanf("%d",&n),Vn=0,H.clear();
      memset(_next,0,sizeof(_next)),En=0;
      memset(D,0,sizeof(D));
      while (n--)
      {
              u=getdata(),v=getdata();
              D[v]++;
              addedgeE(u,v);
      }
      scanf("%d",&Q);
      memset(Qnext,0,sizeof(Qnext)),Qen=0;
      for (i=1;i<=Q;i++)
      {
              u=getdata(),v=getdata();
              addedgeQ(u,v,i),addedgeQ(v,u,i);
      }
      memset(visited,0,sizeof(visited));
      tarjan(1);
      for (i=1;i<=Q;i++) puts(name[ans[i]].c_str());
      return 0;
}