LCA(求两点最近公共祖先,也可以求两点间是否连通且最短距离)

LCA就是求公共祖先。优质博客推荐
但是不推荐它的伪代码,感觉思路没错,但是有点问题。
我随手写了一个,有错欢迎之处

int get(int u)
{
    if(f[u]==u) return u;
    else f[u]=get(f[u]);
}
void dfs(int u,int pre)
{
    //vis[u]=1;//位置1
    for(int i=first[u];i!=-1;i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            dfs(v,u);
            f[v]=u;
        }
    }
    vis[u]=1;//位置2
    for(int i=first2[u];i!=-1;i=e2[i].nex)
    {
        int v=e2[i].v;
        int id=e2[i].id;
        if(!vis[v])
        {
            ans[id]=get(v);
        }
    }
}

vis[u]为什么放哪个地方而不放在f[v]=u前面,因为那样遍历不到根节点。
无向图可以放在位置1和位置2,讲道理,位置1更快。
但是有向图只能放在位置2,否则提前标记自己,但是自己不一定是祖先,因为自己是有向图。

那么公共祖先有什么用呢?
裸题有用,但是大部分都不是,我学了一个求两点间距离,有意思的很。
首先说一下无向图,只需在dfs的时候传递一个deep变量一直逐层加就好了。
然后dis[u]=deep,那么就两点间距离就是dis[u]+dis[v]-2*dis[get(v)]。
那么有向图必需从根节点dfs,无向图可以从任意节点。

无向图求两点距离

hdu2874

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=20005;
const int maxm=2000005;
int n,m,c;

struct node
{
    int v,w,nex;
} e[maxn];
struct node2
{
    int id,v,nex;
} e2[maxm];
int first[maxn/2];
int first2[maxn/2];
int tot,tot2;

int vis[maxn];
int f[maxn];
int dis[maxn];
int ans[maxm/2];
void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void edge2(int id,int u,int v)
{
    e2[tot2].id=id;
    e2[tot2].v=v;
    e2[tot2].nex=first2[u];
    first2[u]=tot2++;
}
void init()
{
    mem(first,-1);
    mem(first2,-1);
    tot=0;
    tot2=0;
    mem(vis,0);
    for(int i=1; i<=n; i++)
    {
        f[i]=i;
    }
    mem(dis,0);
    mem(ans,-1);
}
int get(int u)
{
    if(f[u]==u)
    {
        return u;
    }
    else
    {
        return f[u]=get(f[u]);
    }
}
//void marge(int u,int v)
//{
//    int f1=get(u);
//    int f2=get(v);
//    if(f1!=f2)
//        f[f2]=f1;
//}
int dfs(int u,int pre,int deep,int root)
{
    vis[u]=root;
    dis[u]=deep;
    int v;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        v=e[i].v;
        if(v==pre) continue;
        //printf("%d %d\n",u,v);
        if(!vis[v])
        {
            //printf("       %d\n",v);
            dfs(v,u,deep+e[i].w,root);
            f[v]=u;
        }
    }
    for(int i=first2[u]; i!=-1; i=e2[i].nex)
    {
        v=e2[i].v;
        if(vis[v]==root)
        {
            //printf("           %d %d %d\n",dis[u],dis[v],get(v));
            ans[e2[i].id]=dis[u]+dis[v]-2*dis[get(v)];
        }
    }
}
void LCA()
{
    for(int i=1; i<=n; i++)
    {
        //printf("i=%d\n",i);
        if(!vis[i])
        {
            //printf("i=%d\n",i);
            dfs(i,-1,0,i);
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&c))
    {
        init();
        for(int i=0; i<m; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=c; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            edge2(i,u,v);
            edge2(i,v,u);
        }
        LCA();
        for(int i=1; i<=c; i++)
        {
            if(ans[i]!=-1)
                printf("%d\n",ans[i]);
            else
                printf("Not connected\n");
        }
    }
    return 0;
}

有向图两点间距离

hdu2586

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=40010;
int n,m;
int vis[maxn];
int f[maxn];
//int pre[maxn];
int ans[maxn];
int dis[maxn];
map<string,int>str;
int top;

int tot,tot2;
struct node
{
    int u,v,w,nex;
} e[maxn*10];
int first[maxn];

struct node2
{
    int id;
    int u,v,nex;
} e2[maxn*10];
int first2[maxn];

void edge(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nex=first[u];
    first[u]=tot++;
}
void edge2(int id,int u,int v)
{
    e2[tot2].id=id;
    e2[tot2].u=u;
    e2[tot2].v=v;
    e2[tot2].nex=first2[u];
    first2[u]=tot2++;
}

void init()
{
    tot=tot2=0;
    mem(first,-1);
    mem(first2,-1);
    mem(vis,0);
    for(int i=0; i<=n; i++)
    {
        f[i]=i;
    }
    mem(ans,0);
    top=0;
    //mem(pre,-1);
}
int get(int u)
{
    if(f[u]==u)
        return u;
    else
        return f[u]=get(f[u]);
}
void dfs(int u,int deep,int pre)
{
    vis[u]=1;
    dis[u]=deep;
    for(int i=first[u]; i!=-1; i=e[i].nex)
    {
        int v=e[i].v;
        if(pre==v) continue;
        if(!vis[v])
        {
            dfs(v,deep+e[i].w,u);
            f[v]=u;
        }
    }
    for(int i=first2[u]; i!=-1; i=e2[i].nex)
    {
        int v=e2[i].v;
        int id=e2[i].id;

        if(vis[v])
        {
            ans[id]=dis[u]+dis[v]-2*dis[get(v)];
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int u,v,w;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge(u,v,w);
            edge(v,u,w);
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            edge2(i,u,v);
            edge2(i,v,u);
        }
        dfs(1,0,-1);
        for(int i=1; i<=m; i++)
        {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注