UVA 318 Network（无向图求割点数）

Description

Input

Output

Sample Input

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

Sample Output

1
2

Hint

求割点数：

模板题：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int maxn=110;
const int maxm=110*110;
struct node{
    int to,next;
    bool col;//为桥
}e[maxm];
int head[maxn],cnt;
int DFN[maxn],low[maxn];
int s[maxn],instack[maxn];
int idex,top,bridge;
int col[maxn],add[maxn];//为割；删除点后增加的联通快
int n;
void init()
{
    cnt=top=idex=bridge=0;
    CLEAR(head,-1);
    CLEAR(DFN,0);
    CLEAR(low,0);
    CLEAR(instack,0);
    CLEAR(col,0);
    CLEAR(add,0);
}
void addedge(int u,int v)
{
    e[cnt].to=v;e[cnt].next=head[u];
    e[cnt].col=false;head[u]=cnt++;
}
void Tarjan(int u,int pre)
{
    low[u]=DFN[u]=++idex;

    instack[u]=1;
    int son=0;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(!DFN[v])
        {
            son++;
            Tarjan(v,u);
            if(low[u]>low[v]) low[u]=low[v];
            if(low[v]>DFN[u])//桥
            {
                bridge++;
                e[i].col=true;
                e[i^1].col=true;
            }
            if(u!=pre&&low[v]>=DFN[u])//割点判断1
            {
                col[u]=1;
                add[u]++;
            }
        }
        else if(low[u]>DFN[v])
            low[u]=DFN[v];
    }
    if(u==pre&&son>1)  col[u]=1;//割点判断2
    if(u==pre)  add[u]=son-1;
    instack[u]=0;
    top--;
}
int main()
{
    int u,v;
    while(~scanf("%d",&n)&&n)
    {
        init();
        while(~scanf("%d",&u)&&u)
        {
            while(getchar()!='\n')
            {
                scanf("%d",&v);
                addedge(u,v);
                addedge(v,u);
            }
        }
        REPF(i,1,n)
           if(!DFN[i])  Tarjan(i,i);
        int ans=0;
        REPF(i,1,n)
          if(col[i])  ans++;
        printf("%d\n",ans);
    }
    return 0;
}

UVA 318 Network（无向图求割点数）

原文：http://blog.csdn.net/u013582254/article/details/43155037