Poj 1523 SPF 关节点

 经典的关节点例题，要注意只有1个点的情况

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int org[1001][1001],n;
bool ok;
int dph[1001],low[1001],vis[1001],Ans[1001];
void dfs(int u,int d)//Tarjan
{
    dph[u]=low[u]=d;
    vis[u]=1;
    int ans=0;
    for(int v=1;v<=n;v++)
    {
        if(!org[u][v])continue;
        if(vis[v])
        {
            low[u]=min(low[u],dph[v]);
        }
        else
        {
            dfs(v,d+1);
            if(low[v]>=dph[u])ans++;
            low[u]=min(low[u],low[v]);
        }
    }
    if(u==1&&ans>=1)Ans[u]=ans-1;
    else Ans[u]=ans;
}
int main()
{
    int a,b,T=0;
    while(~scanf("%d",&a)&&a)
    {
        n=0;
        scanf("%d",&b);
        memset(org,0,sizeof(org));
        if(T)puts("");
        T++;
        org[a][b]=org[b][a]=1;
        n=max(n,max(a,b));
        while(~scanf("%d",&a)&&a)
        {
            scanf("%d",&b);
            org[a][b]=org[b][a]=1;
            n=max(n,max(a,b));
        }
        ok=0;
        memset(Ans,0,sizeof(Ans));
        memset(vis,0,sizeof(vis));
        printf("Network #%d\n",T);
        dfs(1,1);
        for(int i=1;i<=n;i++)
        {
            if(Ans[i])
                ok=1,
                printf("  SPF node %d leaves %d subnets\n",i,Ans[i]+1);
        }
        if(!ok)printf("  No SPF nodes\n");
    }
}