Poj1523 无向连通图求割点

题目大意：也是给你一个无向连通图，让你求出该无向图的割点，并求出如果去掉这个割点，该无向图会变成几个连通分量。

算法思路：赤裸裸的tarjan求割点算法，但cnt数组记录的是去掉该点，连通图的连通分量的变化量，因此，如果数组在该点的值不为1，那么说明这个点为割点，但要注意，分成的连通分量数为cnt数组在该点的值+1。但特别要注意的一点，如果根节点是割点的话，那么说明根的度>=2，则这个度就是分成的连通分量数，不必再+1。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 1005
int a[MAXN][MAXN],low[MAXN],dfn[MAXN],cnt[MAXN];
bool visited[MAXN],over,flag;
int num[MAXN];
int l,r,times,n,sum,sym,sym2;
 map<int,bool>maps;
void tarjan(int u)
{
    dfn[u]=low[u]=times++;
    visited[u]=true;
    for(int i=1;i<sym2;i++)
    {
        int v=num[i];
        if(a[u][v])
        {

            if(visited[v])
                low[u]=min(low[u],dfn[v]);
            else
            {
                tarjan(v);
                low[u]=min(low[u],low[v]);
                if(low[v]>=dfn[u]&&u!=1)
                    cnt[u]++;
                else if(u==1)
                    sum++;
            }


        }
    }
}
int main()
{
    sym=1;
   while(true)
   {
        maps.clear();
       sym2=1;
       n=-1;sum=0;
       flag=false;
       memset(cnt,0,sizeof(cnt));
       memset(a,0,sizeof(a));
       memset(dfn,0,sizeof(dfn));
       memset(low,0,sizeof(low));
       memset(visited,false,sizeof(visited));
       memset(num,0,sizeof(num));
       times=0;
        scanf("%d",&l);
        if(l==0&&over)
            break;
       while(true)
       {

           if(l==0)
           {
               over=true;
               break;
           }
           over=false;
           scanf("%d",&r);
           if(l>n)
                n=l;
           if(r>n)
                n=r;
            if(maps.find(l)==maps.end())
            {
                maps[l]=true;
                num[sym2++]=l;
            }
            if(maps.find(r)==maps.end())
            {
                maps[r]=true;
                num[sym2++]=r;
            }
           a[l][r]=a[r][l]=1;
           scanf("%d",&l);

       }
       //for(int i=1;i<=n;i++)
       //{
           tarjan(num[1]);
      // }
        printf("Network #%d\n",sym++);
        if(sum>=2)
        {
            flag=true;
            printf("  SPF node %d leaves %d subnets\n",num[1],sum);
        }
        for(int i=2;i<=n;i++)
        {
            if(cnt[num[i]])
            {
                flag=true;
                printf("  SPF node %d leaves %d subnets\n",num[i],cnt[num[i]]+1);
            }
        }
        if(!flag)
            printf("  No SPF nodes\n");
        printf("\n");
   }

}