Poj1144 tarjan算法求割点

题目大意：给你一个节点从1到n的连通图，问你这个图的割点有多少个。

算法思路：求割点的简单题，求割点也用tarjan算法，但要注意，根如果为割点的话，那么根的度必须大于等于2，其他点判定割点的话当且仅当自己的子节点没有越过自己的回边，也就是low[v]>=dfn[u].

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int a[105][105],dfn[105],low[105],cnt[105],times,sum;
int ans=0;
bool visited[105];
char c;
void tarjan(int u)
{

    int i;
    dfn[u]=low[u]=times++;
    visited[u]=true;
    for(int i=1;i<=n;i++)
    {
        if(a[u][i])
        {
            if(visited[i])
                low[u]=min(low[u],dfn[i]);
            else
            {
                tarjan(i);
                low[u]=min(low[u],low[i]);
                if(low[i]>=dfn[u]&&u!=1)
                    cnt[u]++;
                else if(u==1)
                {
                    sum++;
                }
            }


        }

    }

}
int main()
{
    while(true)
    {
        scanf("%d",&n);
        if(n==0)
            break;
        memset(a,0,sizeof(a));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(visited,false,sizeof(visited));
        memset(cnt,0,sizeof(cnt));

        times=0;
        sum=0;ans=0;
        while(true)
        {

            scanf("%d",&m);
            if(m==0)
                break;
            int flag=0;
            while(scanf("%c",&c))
            {
                if(c=='\n')
                {
                    a[m][flag]=a[flag][m]=1;
                    flag=0;
                    break;
                }
                if('0'<=c&&c<='9')
                {
                    flag=flag*10+(c-'0');
                }
                else if(c==' '&&flag!=0)
                {
                    a[m][flag]=a[flag][m]=1;
                    flag=0;
                }
            }





        }


        tarjan(1);
        for(int i=2;i<=n;i++)
        {
            if(cnt[i])
                ans++;
        }
        if(sum>=2)
        {
            ans++;
        }

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


    }


    return 0;

}