UVA-315 无向图求割点个数

题意抽象：

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

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

考虑一下怎么利用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=110;
const int MAXM=110*110;
int tot=0;
int pointer[MAXN],DFN[MAXN],low[MAXN];
bool instack[MAXN];
int Stap[MAXN];
int Stop,cnt=0,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],0);
    pointer[a]=tot++;
    edge[tot]=Edge(a,pointer[b],0);
    pointer[b]=tot++;
}
void init()
{
    memset(pointer,-1,sizeof(pointer));
    memset(par,-1,sizeof(par));
    memset(iscut,0,sizeof(iscut));
    memset(DFN,0,sizeof(DFN));
    memset(add_block,0,sizeof(add_block));
    tot=0;cnt=0;
    int k,u;char c;
    while(scanf("%d",&u)&&u)
    {
        while(scanf("%d%c",&k,&c)&&k)
        {
            addedge(u,k);
            if(c=='
') break;
        }
    }
}
void tarjan(int u,int pre)
{
    int son=0;
    DFN[u]=low[u]=++cnt;
    for(int j=pointer[u];j!=-1;j=edge[j].next)
    {
        int v=edge[j].to;
        if(edge[j].vis) continue;
        edge[j].vis=1;
        edge[j^1].vis=1;
        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]=1;
                add_block[u]++;
            }
        }
        else if(DFN[v]<low[u]) low[u]=DFN[v];
    }
    if(u==pre&&son>1) iscut[u]=1;
    if(u==pre) add_block[u]=son-1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)&&n)
    {
        init();
        rep(i,1,n) if(!DFN[i]) tarjan(i,i);
        int ans=0;
        rep(i,1,n) if(iscut[i]) ans++;
        printf("%d
",ans);
    }
    return 0;
}