POJ - 1144 输入方式+割点

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 10005
using namespace std;.

int n,tot,dx;
int h[MAXN],low[MAXN],dfn[MAXN],cnt[MAXN],rt,ans;

struct node{
    int from,to,next;
}e[MAXN<<1];

void init(){
    tot=dx=ans=rt=0;
    memset(h,-1,sizeof(h));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(cnt,0,sizeof(cnt));
}

void add(int x,int y){
    tot++;
    e[tot].from=x;
    e[tot].to=y;
    e[tot].next=h[x];
    h[x]=tot;
}

int tarjan(int now,int fa){
    dx++;
    low[now]=dfn[now]=dx;
    for(int i=h[now];i!=(-1);i=e[i].next){
        if(!dfn[e[i].to]){
            tarjan(e[i].to,now);
            low[now]=min(low[now],low[e[i].to]);
            if(now==1)rt++;
            else if(low[e[i].to]>=dfn[now])cnt[now]=1;
        }
        else if(e[i].to!=fa){
            low[now]=min(low[now],dfn[e[i].to]);
        }
    }
}

int main(){
    while(scanf("%d",&n)==1){
        if(n==0)break;
        init();
            int x,y;
        while(scanf("%d",&x)==1&&x){
            while(getchar()!=‘\n‘){
                cin>>y;
                add(x,y);
                add(y,x);
            }
        }
        tarjan(1,1);        
        for(int i=1;i<=n;i++){
            if(cnt[i]==1)ans++;
        }        
        if(rt>1)ans++;
        cout<<ans<<endl;
    }
}