tarjan知识点梳理

tarjan在图论中还是挺重要的.这里就简要的梳理一下tarjan的知识点.

tarjan算法与无向图连通性.

首先说一下图中割点和桥的定义.

桥：也称割边,定义类似,在无向图中,若去掉某条边,导致整张图不连通,则该边为割边.

割点：在无向图中,若去掉某个点,导致整张图不连通,则该点为割点.

其他的什么基础知识就不多说了,这里给出桥和割点的判定法则.

割边:dfn[x]<low[y].

感性的理解下,low[y]说明y向下走,没办法通过非树边到达x及以上的点.代码中的小细节就是tarjan时记录过来的边,防止重边对答案的影响.

割边:dfn[N],low[N],bridge[N],num;

inline void tarjan(int x,int in_edge)

{

    dfn[x]=low[x]=++num;

    for(int i=link[x];i;i=a[i].next)

    {

        int y=a[i].y;

        if(!dfn[y])

        {

            tarjan(y,i);

            low[x]=min(low[x],low[y]);

            if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=true;

        }

        else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);

    }

}

割点:

1.若x不是搜索树的根结点,则满足dfn[x]<=low[y].(感性的理解,y只能到达x,无法与x以上的点取得联系)

2.若x是搜索树的1根结点,则满足至少存在两个以上节点才行.(根只有一个儿子显然不行.)

割点:num,dfn[N],low[N],vis[N];

inline void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    int flag=0;

    for(int i=link[x];i;i=a[i].next)

    {

        int y=a[i].y;

        if(!dfn[y])

        {

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x])

            {

                flag++;

                if(x!=root||flag>=2) vis[x]=1;

            }

        }

        else low[x]=min(low[x],dfn[y]);

    }

}

之后是无向图的双连通分量.

点双联通图:若一个图中不存在割点,则称该图是点双联通图.

点双联通分量：无向图中的极大点双连通图.

边双联通图：若一个图中不存在桥,则称该图是边双联通图.

边双连通分量:无向图中的极大边双联通图.

先讨论边双的情况(因为简单).

判定:一个图是边双连通图的充要条件,图中任意一条边都至少存在一个简单环中.

很显然吧,若不在环中,则该边连接的两个点就断开了,则存在割边,不符合定义.

给出边双联通分量,即缩点的代码：

inline void tarjan(int x,int in_edge)

{

    dfn[x]=low[x]=++num;

    for(int i=link[x];i;i=a[i].next)

    {

        int y=a[i].y;

        if(!dfn[y])

        {

            tarjan(y,i);

            if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=true;

        }

        else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);

    }

}

inline void dfs(int x)

{

    c[x]=dcc;

    for(int i=link[x];i;i=a[i].next)

    {

        int y=a[i].y;

        if(c[y]||bridge[i]) continue;

        dfs(y);

    }

}

main函数内：

for(int i=1;i<=n;++i)  if(!c[i]) dcc++,dfs(i);

for(int i=2;i<=tot;++i)

{

    int x=a[i^1].y,y=a[i].y;

    if(c[x]!=c[y]) add_c(c[x],c[y]);

}

点双连通分量的判定(至少满足一个)：

1.图的顶点数不超过2.

2.图中任意两个节点都同时包含在至少一个简单环中.

证明略过.....(还是太菜了..)

点双的代码：

inline void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    stack[++top]=x;

    if(x==root&&link[x]==0)

    {

        dcc[++cnt].push_back(x);

        return;

    }

    int flag=0;

    for(int i=link[x];i;i=a[i].next)

    {

        int y=a[i].y;

        if(!dfn[y])

        {

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x])

            {

                ++flag;

                if(x!=root||flag>=2) vis[x]=1;

                cnt++;

                int z=0;

                while(z!=y)

                {

                    z=stack[top--];

                    dcc[cnt].push_back(z);

                }

                dcc[cnt].push_back(x);

            }

        }

    }

}

main函数内：

num=cnt;

for(int i=1;i<=n;++i) if(vis[i]) new_id[i]=++num;

tc=1;

for(int i=1;i<=cnt;++i)

{

    for(int j=0;j<dcc[i].size();++j)

    {

        int x=dcc[i][j];

        if(vis[x])

        {

            add_c(i,new_id[x]);

            add_c(new_id[x],i);

        }

        else c[x]=i;

    }

}

放一道边双缩点的题(码量很大啊...)

364. 网络

巴特西

tarjan知识点梳理

最新文章

热门文章