tarjan算法的补充POJ2533tarjan求度

做题时又遇到了疑惑，说明一开始就没有完全理解

基于dfs的tarjan，搜索时会有四种边

树枝边：DFS 时经过的边，即 DFS 搜索树上的边
前向边：与 DFS 方向一致，从某个结点指向其某个子孙的边
后向边：与 DFS 方向相反，从某个结点指向其某个祖先的边
横叉边：从某个结点指向搜索树中另一子树中的某结点的边

Low(u)为 u 或 u 的子树（经过最多一条后向边或栈中横叉边）能够回溯到的最早的栈中结点的次序号。

Low(u)=Min
{
DFN(u),
Low(v),(u,v)为树枝边， u 为 v 的父结点
DFN(v),(u,v)为后向边或指向栈中结点的横叉边
}

所以做更新时要判断边的类别

这篇博客讲的很棒了

https://blog.csdn.net/qianguch/article/details/54710272

所以我在做这道题目的时候，对栈内栈外的没有考虑，所以出错了

#include <iostream>

#include <cstdio>

#include <string.h>

#define inf (1 << 30)

using namespace std;

const int maxn = 5500;

const int maxm = 50500;

struct node{

    int to,pre;

}e[maxm];

int dfn[maxn],low[maxn];

int color[maxn],col;

int id[maxn],cnt;

int idx;

int stk[maxn],s_cnt;

int n,m;

int out[maxn];

bool instk[maxn];

void init()

{

    memset(id,-1,sizeof(id));

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(color,0,sizeof(color));

    memset(out,0,sizeof(out));

    memset(instk,0,sizeof(instk));

    col = idx = cnt = s_cnt = 0;

}

void add(int u,int v)

{

    e[cnt].to = v;

    e[cnt].pre = id[u];

    id[u] = cnt++;

}

void tarjan(int u,int fa)

{

    dfn[u] = low[u] = ++idx;

    stk[s_cnt++] = u;

    instk[u] = 1;

    for(int i = id[u];~i;i = e[i].pre)

    {

        int v = e[i].to;

        if(!dfn[v])

        {

            tarjan(v,u);

            low[u] = min(low[u],low[v]);

        }

        else if(instk[v])//此时表示已经更新过了

        {

            low[u] = min(low[u],dfn[v]);

        }

    }

    if(dfn[u] == low[u])

    {

        col++;

        while(s_cnt > 0 && stk[s_cnt] != u)

        {

            --s_cnt;

            color[stk[s_cnt]] = col;

            instk[stk[s_cnt]] = 0;

        }

    }

}

int main()

{

    int u,v;

    while(~scanf("%d",&n),n)

    {

        scanf("%d",&m);

        init();

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

        {

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

            add(u,v);

        }

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

        {

            if(!dfn[i])

                tarjan(i,-1);

        }

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

        {

            for(int j = id[i];~j;j = e[j].pre)

            {

                int to = e[j].to;

                if(color[i] != color[to])

                {

                    ++out[color[i]];

                }

            }

        }

        bool flag = 1;

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

        {

            if(!out[color[i]])

            {

                if(flag)

                    printf("%d",i),flag = 0;

                else

                    printf(" %d",i);

            }

        }

        printf("\n");

    }

    return 0;

}

巴特西

tarjan算法的补充POJ2533tarjan求度

最新文章

热门文章