MyException - 我的异常网
当前位置:我的异常网» C++ » LCA:倍加与tarjan

LCA:倍加与tarjan

www.MyException.Cn  网友分享于:2013-10-08  浏览:0次
LCA:倍增与tarjan

学了好久(一两个星期)都没彻底搞懂的lca,今天总算理解了。就来和大家分享下我自己的心得

首先,如果你还不懂什么是lca,出门左转自行百度

首先讲倍增

倍增的思想很简单,首先进行预处理,用一个深搜将每个点的深度和它向上跳一步到达的点(也就是它的父节点)处理出来,然后用下列递推式

f[i][j]=f[f[i][j-1]][j-1]

求出该点跳2^j步所到达的点。这里解释一下,为什么是f[f[i][]j-1][j-1]?因为倍增每次都是跳的2的整数次幂步,而2^j=2^(j-1)+2^(j-1);这样就不难理解了。

然后,对于每两个询问的点,只需要先找出那个点的深度更深,就将它跳跃到与另一个点深度相同,如果此时两个点相同,那么这个点就是最近公共祖先;如果不相同,两个点就一起跳,直找到最近公共祖先为止。

废话少说,上代码:

---------------------------------------------------------分割线-----------------------------------------------------

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 500005
using namespace std;
int n,m,s,d[N],f[N][20],head[N];
struct Edge{
int from,to,next;
}edge[N*2];
inline int read()
{
    char ch=getchar();int num=0;
    if(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
    {num=num*10+ch-'0';
    ch=getchar();}
    return num;
}
int anum=1;
void add(int x,int y)
{edge[anum].to=y;
edge[anum].next=head[x];
head[x]=anum++;}
void dfs(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int ne=edge[i].to;
        if(d[ne]==0)
        {d[ne]=d[u]+1;
        f[ne][0]=u;
        dfs(ne);}
    }
}
void init()
{
    for(int i=1;i<=19;i++)
    {
        for(int j=1;j<=n;j++)
        {f[j][i]=f[f[j][i-1]][i-1];}
    }
}
int lca(int a,int b)
{
    if(d[a]<d[b]) swap(a,b);
    for(int i=19;i>=0;i--)
    {if(d[f[a][i]]>=d[b])
    a=f[a][i];}
    if(a==b) return a;
    for(int i=19;i>=0;i--)
    if(f[a][i]!=f[b][i])
    a=f[a][i],b=f[b][i];
    return f[a][0];
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();s=read();
    for(int i=1;i<n;i++)
    {int x,y;
    x=read();y=read();
    add(x,y);add(y,x);}
    d[s]=1;
    dfs(s);init();
    for(int i=1;i<=m;i++)
    {int a,b;
    a=read();b=read();
    printf("%d\n",lca(a,b));}
    return 0;
}

 

-----------------------------------------------------------------分割线-------------------------------------------------------------------------------

关于tarjan,具体思想我在另外一篇博客中已经讲过了,这里就只放代码,思路请转:http://www.cnblogs.com/cytus/p/7524594.html

下面是代码:

 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define N 500005
#define M 1000001
using namespace std;
int n,m,s,cnt1,cnt2;
int dad[N],ans[N];
bool used[N];
struct edge{
int v,num,next;
}e1[M],e2[M];
struct road{
int head;
}v1[N],v2[N];
void before()
{
    memset(v1,-1,sizeof(v1));
    memset(v2,-1,sizeof(v2));
    memset(used,false,sizeof(used));
    memset(dad,-1,sizeof(dad));
}
int find(int x)
{
    return dad[x]==-1?x:dad[x]=find(dad[x]);
}
void together(int x,int y)
{
    int f1=find(x);
    int f2=find(y);
    if(f1!=f2)
    dad[y]=x;
}
void v1add(int x,int y)
{
    e1[cnt1].v=y;
    e1[cnt1].next=v1[x].head;
    v1[x].head=cnt1++;
}
void v2add(int x,int y,int z)
{
    e2[cnt2].v=y;
    e2[cnt2].num=z;
    e2[cnt2].next=v2[x].head;
    v2[x].head=cnt2++;
}
void tarjan(int u)
{
    used[u]=true;
    for(int i=v1[u].head;i!=-1;i=e1[i].next)
    {
        int v=e1[i].v;
        if(used[v]) continue;
        tarjan(v);
        together(u,v);
    }
    int sum;
    for(int i=v2[u].head;i!=-1;i=e2[i].next)
    {
        int v=e2[i].v;
        sum=e2[i].num;
        if(used[v])
        ans[sum]=find(v);
    }
}
int main()
{
    int u,v;
    scanf("%d%d%d",&n,&m,&s);
    before();
    int nn=n;
    nn--;
    while(nn--)
    {
    scanf("%d%d",&u,&v);
    v1add(v,u);v1add(u,v);
    }
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d",&u,&v);
    v2add(u,v,i);v2add(v,u,i);
    }
    tarjan(s);
    for(int i=1;i<=m;i++)
    printf("%d\n",ans[i]);
    return 0;
}

 

文章评论

什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
编程语言是女人
编程语言是女人
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
 程序员的样子
程序员的样子
鲜为人知的编程真相
鲜为人知的编程真相
漫画:程序员的工作
漫画:程序员的工作
程序员都该阅读的书
程序员都该阅读的书
程序员必看的十大电影
程序员必看的十大电影
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
老程序员的下场
老程序员的下场
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
代码女神横空出世
代码女神横空出世
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
中美印日四国程序员比较
中美印日四国程序员比较
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
10个调试和排错的小建议
10个调试和排错的小建议
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
一个程序员的时间管理
一个程序员的时间管理
程序员的鄙视链
程序员的鄙视链
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
如何成为一名黑客
如何成为一名黑客
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
旅行,写作,编程
旅行,写作,编程
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
每天工作4小时的程序员
每天工作4小时的程序员
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
我的丈夫是个程序员
我的丈夫是个程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有