顶点u是割点的充要条件是：u是深度优先树上有两个以上子女的的根，或者不是根时有一个子女w满足low[w]>=dfn[u]，
low[u]是从u到u的子孙出发通过back edge 可达的最低深度优先数。
low[u]=min{
dfn[u],
min{ low[w] | w是u的一个子女}，
min{dfn[v] | v是u邻接，且(u,v)是一条回边}
}
//Tarjan for solving cut-vertex on undirection graph
#include <cstdio>
#include <string.h>
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=1002;
int map[maxn][maxn];
int vis[maxn];
int dfn[maxn],low[maxn];
int nodes,tmpdfn;
int son , subnets[maxn];//
int cas=0;
void dfs (int u)
{
for (int v=1 ; v<=nodes ; v++)
{
if(map[u][v])
{
if(!vis[v])//v is not visited ,v is u's son
{
vis[v]=1;
dfn[v]=low[v]= (++tmpdfn);
dfs(v);
low[u]=min(low[v],low[u]);
if(low[v]>=dfn[u])
{
if(u!=1)subnets[u]++;
if(u==1)son++;
}
}
else low[u]=min(low[u],dfn[v]);//v has already visited ,<v,u> is a back edge
}
}
}
void init ()
{
low[1]=dfn[1]=1;
tmpdfn=1;
son=0;
memset (vis,0,sizeof(vis));
vis[1]=1;
memset (subnets,0,sizeof(subnets));
}
int main ()
{
int u,v,i;
bool find ;
while (scanf("%d",&u),u)
{
memset(map,0,sizeof(map));
nodes=0;
nodes=max(nodes,u);
scanf("%d",&v);
nodes=max(nodes,v);
map[u][v]=map[v][u]=1;
while (scanf("%d",&u),u)
{
scanf("%d",&v);
nodes=max(nodes,u);
nodes=max(nodes,v);
map[u][v]=map[v][u]=1;
}
if(cas>=1)printf("\n");
printf("Network #%d\n",++cas);
init ();
//printf("%d\n",nodes);
dfs(1);
if(son>1) subnets[1]=son-1;
find=0 ;
for (i=1 ; i<=nodes ; ++i)
{
if(subnets[i])
{
find=1 ;
printf(" SPF node %d leaves %d subnets\n",i,subnets[i]+1);
}
}
if(!find)printf(" No SPF nodes\n");
}
return 0;
}