poj3713 Transferring Sylla 枚举+tarjan判割点

其实就是判断是否为三连通图

三连通图指的是去掉3个点就不连通的图，但是并没有直接求三连通的算法。著名的Tarjan算法可以求解连通和割点，再枚举删除一个点就能达到三连通的目的。

先看用例2，是由用例1去掉一条边而变成非三连通图的：

至少造成了2和3非三连通：

我们来思考如何推导出2和3非三连通，假设从上图中删除了节点0，通过Tarjan算法，我们可以发现节点1是割点：

那么只需删除从3到割点和从3到我们枚举删除的节点0的两条边，就可以将3和2分割开来：

才删除了两条边2和3就不连通了，这个图显然不是三连通图。

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

const int maxn = ;

int cnt,flag,times,del,root;

int head[maxn],low[maxn],dfn[maxn];

struct no

{

    int v,next;

}Eg[*maxn];

void init( )

{

    cnt=;

    memset(head,-,sizeof(head));

}

void add(int form,int to)

{

    Eg[cnt].v=to;Eg[cnt].next=head[form];head[form]=cnt++;

}

void dfs(int u,int fa)

{

    if(flag)

    return ;

    int tot=;

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

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

    {

        int v=Eg[i].v;

        if(v==fa||v==del)

        continue;

        if(!dfn[v])

        {

            tot++;

            dfs(v,u);

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

            //判断割点

            if((u==root&&tot>)||(u!=root&&low[v]>=dfn[u]))

                flag=;

        }

        else

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

    }

}

int main( )

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==&&m==)

            break;

    init();

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

    {

        int u,v;

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

        add(u,v);

        add(v,u);

    }

    flag=;

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

    {

        del = i ; times = ;

        memset(dfn,,sizeof(dfn));

        root = ;

        if(del==)

        root=;

        dfn[del] = ;

        dfs(root,-);

        for(int j= ; j<n ; j++)

        {

            if(!dfn[j])

            {

                flag=;

                break;

            }

        }

        if(flag)

            break;

    }

    if(flag)

        puts("NO");

    else

        puts("YES");

    }

    return ;

}

巴特西

poj3713 Transferring Sylla 枚举+tarjan判割点

最新文章

热门文章