poj1523割顶-点双联通

题意：求出所有的割顶，而且还有输出该割顶连接了几个点双连通分量

题解：直接tarjan求点双联通分量就好了，可以在加入边的时候记录加入次数，大于1的都是桥，输入输出很恶心，注意格式

#include<map>

#include<set>

#include<list>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

using namespace __gnu_cxx;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

map<int,int>ma[N];

vector<int>v[N],bcc[N];

int dfn[N],low[N];

int index,num;

int bccno[N],iscut[N];

struct edge{int from,to;};

stack<edge>s;

void tarjan(int u,int f)

{

    low[u]=dfn[u]=++index;

    for(int i=;i<v[u].size();i++)

    {

        int x=v[u][i];

        edge e=(edge){u,x};

        if(x==f)continue;

        if(!dfn[x])

        {

            s.push(e);

            tarjan(x,u);

            low[u]=min(low[u],low[x]);

            if(low[x]>=dfn[u])

            {

                num++;bcc[num].clear();

                for(;;)

                {

                    edge p=s.top();s.pop();

                    if(bccno[p.from]!=num)

                    {

                        bccno[p.from]=num;

                        bcc[num].pb(p.from);

                        iscut[p.from]++;

                    }

                    if(bccno[p.to]!=num)

                    {

                        bccno[p.to]=num;

                        bcc[num].pb(p.to);

                        iscut[p.to]++;

                    }

                    if(p.from==e.from&&p.to==e.to)break;

                }

            }

        }

        else

        {

            if(dfn[x]<dfn[u])low[u]=min(low[u],dfn[x]);

        }

    }

}

void init()

{

    memset(dfn,,sizeof dfn);

    memset(low,,sizeof low);

    memset(bccno,,sizeof bccno);

    memset(iscut,,sizeof iscut);

    index=num=;

    for(int i=;i<=;i++)

    {

        v[i].clear();

        bcc[i].clear();

        ma[i].clear();

    }

    while(!s.empty())s.pop();

}

int main()

{

    int a,b,n=,cnt=;

    while(~scanf("%d",&a))

    {

        if(a==)break;

        init();

        scanf("%d",&b);

        n=max(n,max(a,b));

        v[a].pb(b);

        v[b].pb(a);

        ma[a][b]=ma[b][a]=;

        while(~scanf("%d",&a))

        {

            if(a==)break;

            scanf("%d",&b);

            n=max(n,max(a,b));

            if(!ma[a][b])

            {

                v[a].pb(b);

                v[b].pb(a);

                ma[a][b]=ma[b][a]=;

            }

        }

        for(int i=;i<=n;i++)

            if(!dfn[i])

                tarjan(i,-);

      /*  cout<<num<<endl;

        for(int i=1;i<=num;i++)

        {

            for(int j=0;j<bcc[i].size();j++)

                cout<<bcc[i][j]<<" ";

            cout<<endl;

        }*/

        printf("Network #%d\n",++cnt);

        bool ok=;

        for(int i=;i<=n;i++)

        {

            if(iscut[i]>)

            {

                ok=;

                printf("  SPF node %d leaves %d subnets\n",i,iscut[i]);

            }

        }

        if(!ok)printf("  No SPF nodes\n");

puts("");

    }

    return ;

}

/************

************/