Tarjan求LCA胡乱写的板子 x

首先Tarjan算法的基本思路：

　　　　　　 1.任选一个点为根节点，从根节点开始。

　　　　　　2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

　　　　　　3.若是v还有子节点，继续搜索下去，否则下一步。

　　　　　　4.合并v到u上。

　　　　　　5.寻找与当前点u有询问关系的点v。

　　　　　　6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int N = ;

const int M = ;

int top,dad[N];

bool used[N];

struct heads {

    int head;

}v1[N],v2[N];

struct Edge {

    int v,next;

}e1[M],e2[M];

void chu()

{

    memset(v1,-,sizeof(v1));

    memset(v2,-,sizeof(v2));

    memset(dad,-,sizeof(dad));

    memset(used,,sizeof(used));

}

int getdad(int x)

{return dad[x] == - ? x : dad[x] = getdad(dad[x]);}

void Unions(int a,int b)

{

    int r1=getdad(a);

    int r2=getdad(b);

    if(r1!=r2)

        dad[r2]=r1;

}

void add1(int u,int v)

{

    e1[top].v=v;

    e1[top].next=v1[u].head;

    v1[u].head=top++;

}

void add2(int u,int v)

{

    e2[top].v=v;

    e2[top].next=v2[u].head;

    v2[u].head=top++;

}

void Tarjan(int u)

{

    used[u]=true;

    for(int i=v2[u].head;i!=-;i=e2[i].next)

    {

        int v=e2[i].v;

        if(used[v])///无序输出

            printf("The LCA of (%d,%d) is -> %d\n",u,v,getdad(v));

    }

    for(int i=v1[u].head;i!=-;i=e1[i].next)

    {

        int v=e1[i].v;

        if(used[v])

            continue;

        Tarjan(v);

        Unions(u,v);

    }

}

int main()

{

    int n,m,u,v;///n个点,m条边,uv进行连接

    int q;///q次询问

    scanf("%d%d",&n,&m);

    chu();///初始化

    while(m--)

    {

        scanf("%d%d",&u,&v);

        add1(u,v),add1(v,u);

    }

    scanf("%d",&q);

    top=;

    while(q--)

    {

        scanf("%d%d",&u,&v);

        add2(u,v),add2(v,u);

    }

    Tarjan();

    return ;

}

巴特西

Tarjan求LCA胡乱写的板子 x

最新文章

热门文章