HDU4547(CD操作)LCA+Tarjan离线算法 (二)

/*
*题目大意:
*题目为天朝文字,不多说;
*
*算法思想:
*题目很明显要求的是一个LCA问题;
*即询问从A到B的需要的步数,即首先从A到达A和B的最近公共祖先需要的步数+1就OK了;
*
*算法步骤:
*由于是有向图,所以开始可以用一个数组ind记录每个顶点的入度;
*如果该顶点的入度为0,则可以当做根节点,利用dfs求出树中每个顶点的深度d;
*则从u到v的步数ans=d[u]-lca(u,v)+1,当然要考虑几个特殊情况;
**/

#include
#include
#include
#include
#include

const int N=400010;

int p[N];//并查集的父节点
int ind[N];//求顶点的入度,判断根节点
int head[N];
int qhead[N];//询问
bool visit[N];

int d[N];

struct node
{
int to;
int w;
int next;
int lca;
int num;
};

struct query//记录查询
{
int u;
int v;
int lca;
} q[N];

node edge[N];
node qedge[N];//询问边

int n,m;
int cnt1,cnt2;
int cnt;

map Map;

int get_num(string s)//返回每个人对应结点
{
if(Map.find(s)==Map.end())//没有搜索到该键值
{
Map[s]=++cnt;//对应建图
}
// cout<<" Map["< return Map[s];
}

inline void Addedge(int u,int v,int w)
{
edge[cnt1].w=w;
edge[cnt1].to=v;
edge[cnt1].next=head[u];
head[u]=cnt1;
cnt1++;

edge[cnt1].w=w;
edge[cnt1].to=u;
edge[cnt1].next=head[v];
head[v]=cnt1;
cnt1++;
}

inline void Addqedge(int u,int v,int num)
{
qedge[cnt2].num=num;
qedge[cnt2].to=v;
qedge[cnt2].next=qhead[u];
qhead[u]=cnt2;
cnt2++;

qedge[cnt2].num=num;
qedge[cnt2].to=u;
qedge[cnt2].next=qhead[v];
qhead[v]=cnt2;
cnt2++;
}

void dfs(int u,int f,int w)
{
d[u]=w;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
if(v==f)
continue;
dfs(v,u,w+edge[i].w);
}
}

int Find(int x)
{
if(p[x]!=x)
p[x]=Find(p[x]);
return p[x];
}

void Tarjan_LCA(int u)//离线LCA算法
{
p[u]=u;
visit[u]=1;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
if(!visit[edge[i].to])
{
Tarjan_LCA(edge[i].to);
p[edge[i].to]=u;
}
}

for(int i=qhead[u]; i!=-1; i=qedge[i].next)
{
if(visit[qedge[i].to])
{
qedge[i].lca=Find(qedge[i].to);
qedge[i^1].lca=qedge[i].lca;
//printf("%d和%d的最近公共祖先为: %d\n",u,qedge[i].to,qedge[i].lca);
q[qedge[i].num].lca=qedge[i].lca;
}
}
}

void Solve()
{
for(int i=0; i<=n; i++)
{
p[i]=i;
}
memset(head,-1,sizeof(head));
memset(qhead,-1,sizeof(qhead));
memset(visit,0,sizeof(visit));
memset(ind,0,sizeof(ind));
cnt=cnt1=cnt2=0;
int u,v,w;
string s1,s2;
Map.clear();
for(int i=1; i {
cin>>s1>>s2;
u=get_num(s1);
v=get_num(s2);
Addedge(u,v,1);
ind[u]++;
}

for(int i=0; i {
cin>>s1>>s2;
u=get_num(s1);
v=get_num(s2);
/*cout< printf("==%d\n",u);
cout< printf("==%d\n",v);*/
Addqedge(u,v,i);
q[i].u=u;
q[i].v=v;
}

int root=0;
for (int i=1; i<=n; i++)
{
if(ind[i]==0)
{
root=i;
}
}
//printf("root==%d\n",root);
dfs(root,-1,0);
//for(int i=1; i<=n; i++)
//printf("d[%d]==%d\n",i,d[i]);