UVA-315 无向图求割点个数

时间：2023-06-23 13:16:08

题意抽象：

给定一个无向图，输出割点个数。

割点定义：删除该点后，原图变为多个连通块。

考虑一下怎么利用tarjan判定割点：

对于点u和他相连的当时还未搜到的点v，dfs后如果DFN[u]<=low[v]，那么u是割点。（搜v得到的是一个不会倒卷回来的子图）

另外注意一下tarjan搜索时的起始点如果有多个儿子那么它也是割点。

AC代码：

#include<cstdio>

#include<cstring>

#define rep(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int MAXN=;

const int MAXM=*;

int tot=;

int pointer[MAXN],DFN[MAXN],low[MAXN];

bool instack[MAXN];

int Stap[MAXN];

int Stop,cnt=,n;

int par[MAXN];bool iscut[MAXN];

int add_block[MAXN];

struct Edge

{

    int to,next,vis;

    Edge() {}

    Edge(int b,int nxt,int visit) {to=b;next=nxt,vis=visit;}

}edge[MAXM];

inline void addedge(int a,int b)

{

    edge[tot]=Edge(b,pointer[a],);

    pointer[a]=tot++;

    edge[tot]=Edge(a,pointer[b],);

    pointer[b]=tot++;

}

void init()

{

    memset(pointer,-,sizeof(pointer));

    memset(par,-,sizeof(par));

    memset(iscut,,sizeof(iscut));

    memset(DFN,,sizeof(DFN));

    memset(add_block,,sizeof(add_block));

    tot=;cnt=;

    int k,u;char c;

    while(scanf("%d",&u)&&u)

    {

        while(scanf("%d%c",&k,&c)&&k)

        {

            addedge(u,k);

            if(c=='\n') break;

        }

    }

}

void tarjan(int u,int pre)

{

    int son=;

    DFN[u]=low[u]=++cnt;

    for(int j=pointer[u];j!=-;j=edge[j].next)

    {

        int v=edge[j].to;

        if(edge[j].vis) continue;

        edge[j].vis=;

        edge[j^].vis=;

        if(!DFN[v])

        {

            son++;

            par[v]=j;

            tarjan(v,u);

            if(low[v]<low[u]) low[u]=low[v];

            if(DFN[u]<=low[v]&&u!=pre)

            {

                iscut[u]=;

                add_block[u]++;

            }

        }

        else if(DFN[v]<low[u]) low[u]=DFN[v];

    }

    if(u==pre&&son>) iscut[u]=;

    if(u==pre) add_block[u]=son-;

}

int main()

{

    //freopen("in.txt","r",stdin);

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

    {

        init();

        rep(i,,n) if(!DFN[i]) tarjan(i,i);

        int ans=;

        rep(i,,n) if(iscut[i]) ans++;

        printf("%d\n",ans);

    }

    return ;

}

相关文章