学步园

这道题的输入异常鬼畜。= =无法直视

题意：给一个图。输出割点以及删掉割点后形成几个连通块

还是忍不住吐槽：异常鬼畜的输入，还有输出，一不注意就PE

还有，注意到这道题的点不是按顺序给定你的。你需要建立一个point数组来存储点。代码如下。= = 套个模板一不小心就WA了。鬼畜的题、

//author: CHC
//First Edit Time:	2014-07-07 21:33
//Last Edit Time:	2014-07-07 21:33
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 1010
vector <int> e[MAXN];
int dfn[MAXN],low[MAXN],pre[MAXN],n,m;
bool gedian[MAXN];
int times=0,tot=0;
char vis[MAXN];
int point[MAXN];
void tarjan_3(int u){
    dfn[u]=low[u]=++times;
    for(int i=0;i<(int)e[u].size();i++){
        int v=e[u][i];
        if(!dfn[v]){
            pre[v]=u;
            tarjan_3(v);
            low[u]=min(low[u],low[v]);
        }
        else if(pre[u]!=v){
            //else also can ac
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void solve(){
    times=tot=0;
    memset(dfn,0,sizeof(dfn));
    memset(gedian,0,sizeof(gedian));
    memset(pre,0,sizeof(pre));
    tarjan_3(point[1]);
    //gedian 
    int cnt=0;
    for(int i=2;i<=point[0];i++){
        if(pre[point[i]]==point[1]) cnt++;
        else if(dfn[pre[point[i]]]<=low[point[i]])gedian[pre[point[i]]]=true;
    }
    if(cnt>1)gedian[point[1]]=true;
    /*
    for(int i=1;i<=n;i++){
        if(gedian[i])
        printf("%d ",i);
    }
    puts("\n");
    */
    return ;
}
void Addpoint(int x){
    if(vis[x])return ;
    vis[x]=1;
    int &num=point[0];
    point[++num]=x;
}
char vis1[MAXN];
void bfs(int x,int dian){
    queue <int> q;
    q.push(x);
    vis1[x]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<(int)e[now].size();i++){
            int next=e[now][i];
            if(next==dian)continue;
            if(vis1[next])continue;
            //printf("%d ---> %d\n",now,next);
            vis1[next]=1;
            q.push(next);
        }
    }
}
int main()
{
    int x,y;
    int cas=0;
    int ff=1;
    while(~scanf("%d",&x)){
        if(x==0){
            if(ff==0)break;
            printf("Network #%d\n",++cas);
            puts("  No SPF nodes");
            puts("");
            ff=x;
            continue;
        }
        scanf("%d",&y);
        if(y==0)break;
        for(int i=0;i<MAXN;i++)e[i].clear();
        memset(vis,0,sizeof(vis));
        point[0]=0;
        e[x].push_back(y);
        e[y].push_back(x);
        Addpoint(x);
        Addpoint(y);
        while(~scanf("%d",&x)&&x){
            scanf("%d",&y);
            e[x].push_back(y);
            e[y].push_back(x);
            Addpoint(x);
            Addpoint(y);
        }
        ff=x;
        solve();
        int flag=0;
        printf("Network #%d\n",++cas);
        for(int i=1;i<=point[0];i++)
            if(gedian[point[i]]){
                int ans=0;
                memset(vis1,0,sizeof(vis1));
                for(int j=1;j<=point[0];j++){
                    if(point[j]==point[i])continue;
                    if(!vis1[point[j]]){
                        bfs(point[j],point[i]);
                        ans++;
                        //printf("point:%d\n",point[j]);
                    }
                }
                printf("  SPF node %d leaves %d subnets\n",point[i],ans);
                flag=1;
            }
        if(!flag){
            puts("  No SPF nodes");
        }
        puts("");
    }
    return 0;
}