POJ 1144 Network

题目链接： http://poj.org/problem?id=1144

思路：割点板子，此题数据读入有些小毒瘤。

#include <cstdio>
#include <cctype> 
#include <cstring>
#include <set>
#include <iostream>
static const int MAXN=15000;
static const int MAXM=505000;
struct Edge
{
    int to,nextt;
}edge[MAXM];
int n,u,v,num,cnt,ans,head[MAXN],dfn[MAXN],low[MAXN];
std::set<int> s;
inline int get_min(int a,int b){return a<b?a:b;}
inline void addedge(int u,int v)
{
    edge[++num].to=v;
    edge[num].nextt=head[u];
    head[u]=num;
}
inline bool check(int u,int fa,int to,int child){return (u==fa&&child>=2)||(u!=fa&&low[to]>=dfn[u])?true:false;}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++cnt;
    int child=0;
    for(int i=head[u];i;i=edge[i].nextt)
    {
        int to=edge[i].to;
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=get_min(low[u],low[to]);
            if(u==fa) child++;
            if(check(u,fa,to,child)) s.insert(u);
        }
        else low[u]=get_min(low[u],dfn[to]);
    }
}
inline void init()
{
    ans=0;
    cnt=0;
    s.clear();
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(head,0,sizeof(head));
    memset(edge,0,sizeof(edge));
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        while(~scanf("%d",&u)&&u)
        {
            while(getchar()!='\n')
            {
                scanf("%d",&v);
                addedge(u,v);
                addedge(v,u);
            }
        }
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
        printf("%lu\n",s.size());
        init();
    }
}