看了好多dalao的博客,就总结一下啦ovo
tarjian算法很是神奇,它的作用是求lca。它是一种离线算法。
在线是指输入一个询问输出一个结果。
离线是将询问一次性输入,一起处理。
tarjan它是将m个询问打乱顺序,在每个结点上挂上它的询问,利用dfs和并查集进行处理。
对于一个结点u,如果要找(u,v)的lca,u和v的关系分为以下几种情况:
(1)结点v在u的子树中,那么lca(u,v)=u;
(2) 结点v不在u的子树中,那么v就在u子结点以外的结点中。v可能在u的爸爸的子树中,那么lca(u,v)=u的爸爸;
(3)如果v不在u的爸爸的子树中,那么v可能在u的爸爸的爸爸的子树中,lca(u,v)=u的爸爸的爸爸;
发现找爸爸的过程好像和并查集的操作很像哦.
【代码】
#include<bits/stdc++.h>
using namespace std;
#define N 10000
vector<int>vec[N];
vector<int>que[N];
int dad[N],far[N],qx[N],qy[N];
int n,m,x,y,ans[N];
int f(int x)
{
return far[x]==x?x:far[x]=f(far[x]);
}
void dfs(int x)
{
far[x]=x;
for(int i=0;i<vec[x].size();i++)
{
if(dad[x]!=vec[x][i])
{
dad[vec[x][i]]=x;
dfs(vec[x][i]);
}
}
for(int i=0;i<que[x].size();i++)
{
if(dad[y=qx[que[x][i]]^qy[que[x][i]]]^x)//y是x结点的一个询问;x^x^y=y;
{
ans[que[x][i]]=f(y);
}
}
far[x]=dad[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
vec[x].push_back(y);
vec[y].push_back(x);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&qx[i],&qy[i]);
que[qx[i]].push_back(i);//在每个结点上挂上它的询问是第几个询问;
que[qy[i]].push_back(i);
}
dfs(1);
for(int i=1;i<=m;i++)
{
printf("%d ",ans[i]);//每个询问的答案’
}
return 0;
}
原文链接: https://www.cnblogs.com/zzyh/p/6812209.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/253579
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!