UVA315 Network 连通图割点

题目大意：有向图求割点

题目思路：

一个点u为割点时当且仅当满足两个两个条件之一：

1.该点为根节点且至少有两个子节点

2.u不为树根，且满足存在(u,v)为树枝边(或称 父子边，即u为v在搜索树中的父亲)，使得 dfn(u)<=low(v)。

然后注意读入，很容易RE

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXSIZE 1005
#define LL long long

using namespace std;

int vis[MAXSIZE],Map[MAXSIZE][MAXSIZE],low[MAXSIZE],dfn[MAXSIZE],pre[MAXSIZE],Time,n,ans,son;

void Tarjan(int u,int fa)
{
    pre[u]=fa;
    low[u]=dfn[u]=++Time;
    for(int i=1; i<=n; i++)
    {
        if(!Map[u][i] || u==i) continue;
        if(!dfn[i])
        {
            Tarjan(i,u);
            low[u]=min(low[u],low[i]);
        }
        else if(fa!=i)
        {
            low[u]=min(low[u],dfn[i]);
        }
    }
}

void Init()
{
    memset(Map,0,sizeof(Map));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    Time=0;
    ans=0;
    son=0;
}

int main()
{
    int a,b;
    char ch,op;
    while(scanf("%d",&n),n)
    {
        Init();
        getchar();
        while(scanf("%d",&a),a)
        {
            while(scanf("%d%c",&b,&op))
            {
                Map[a][b]=Map[b][a]=1;
                if(op=='
') break;
            }
        }
        Tarjan(1,0);
        for(int i=2;i<=n;i++)
        {
            if(pre[i]==1)
                son++;
            else if(dfn[pre[i]] <= low[i])
                vis[pre[i]]=1;
        }
        if(son > 1) ans++;
        for(int i=2;i<=n;i++)
            if(vis[i]) ans++;
        printf("%d
",ans);
    }
    return 0;
}