图论-最近公共祖先-离线Tarjan算法

有关概念:
  最近公共祖先(LCA,Lowest Common Ancestors):对于有根树T的两个结点u、v,最近公共祖先表示u和v的深度最大的共同祖先。

  Tarjan是求LCA的离线算法(先存储所有询问,再进行运算)

思路:
  从根结点开始DFS,对遍历到的结点u标记已访问,创建新集合,元素为u,再遍历u的每一个儿子,回溯时将每个儿子的集合并到u的集合上,用并查集记录集合中的每个元素的fa为u,接着处理询问,对于关于u的每一个询问,若另一个结点v已访问,则可断定LCA(u,v)为fav,记录结果,最后按顺序输出即可

  dis存储该结点到根结点的距离,用于计算两点之间的路径长度

样例推导(样例来自@SHHHS):

求8、6,9、7的LCA

图论-最近公共祖先-离线Tarjan算法

从根结点1进入,标记访问,创建集合

图论-最近公共祖先-离线Tarjan算法

访问2、4,回溯到2,新集合包含两个结点

图论-最近公共祖先-离线Tarjan算法

访问5、8,处理8的询问,但6未访问,跳过

访问9,处理询问,7未访问,跳过,5、8和9并入2的集合(即fa值设为2)

图论-最近公共祖先-离线Tarjan算法

访问6,处理询问,LCA(8,6)为fa8,即2

访问10,回溯,并入6的集合

图论-最近公共祖先-离线Tarjan算法

回溯,并入2的集合

并入1的集合

图论-最近公共祖先-离线Tarjan算法

访问3、7,处理询问,LCA(7,9)为fa9,即1

图论-最近公共祖先-离线Tarjan算法

回溯,并入3的集合

并入1的集合

图论-最近公共祖先-离线Tarjan算法

 #include<cstdio>
#define MAXN
#define MAXQ
int n,Q,heade[MAXN],headq[MAXN],fa[MAXN],lca[MAXQ],dis[MAXN],cnt;
bool vis[MAXN];
struct edge
{
int v,next,val;
}e[MAXN*];
struct query
{
int u,v,next;
}q[MAXQ*];
void adde(int x,int y,int z)
{
e[++cnt].v=y;
e[cnt].next=heade[x];
heade[x]=cnt;
e[cnt].val=z;
}
void addq(int x,int y)
{
q[++cnt].u=x;
q[cnt].v=y;
q[cnt].next=headq[x];
headq[x]=cnt;
}
int getfa(int x)//并查集路径压缩
{
return fa[x]=x==fa[x]?x:getfa(fa[x]);
}
int getdis(int i)//计算路径长度
{
return dis[q[i<<].u]+dis[q[i<<].v]-*dis[lca[i]];
}
void Tarjan(int u)
{
fa[u]=u;
vis[u]=true;
for(int i=heade[u];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
dis[v]=dis[u]+e[i].val;
Tarjan(v);
fa[v]=u;
}
}
for(int i=headq[u];i;i=q[i].next)//处理询问
{
int v=q[i].u==u?q[i].v:q[i].u;
if(vis[v])lca[i>>]=getfa(fa[v]);
}
}
int main()
{
scanf("%d",&n);
int x,y,z;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
adde(x,y,z);
adde(y,x,z);
}
cnt=;
scanf("%d",&Q);
for(int i=;i<=Q;i++)
{
scanf("%d%d",&x,&y);
addq(x,y);
addq(y,x);
}
Tarjan();
for(int i=;i<=Q;i++)
{
printf("%d\n",getdis(i));
}
return ;
}
上一篇:jQuery选择器(基本过滤选择器)第三节


下一篇:仿酷狗音乐播放器开发日志十九——CTreeNodeUI的bug修复二(附源码)