poj : http://poj.org/problem?id=1523
如果无向图中一个点 u 为割点 则u 或者是具有两个及以上子女的深度优先生成树的根，或者虽然不是一个根，但是它有一个子女 w， 使得low[w] >= dfn[u];
其中low[u] 是指点 u 通过回边所能达到的 最小深度优先数，dfn[u]是指 点u 当前所处的 深度优先数；
low[u] 是在递归回退时计算出来的，dfn[u] 是在递归时直接计算的。
low[u] = min
{
dfn[u];
min{ low[w] } // w是u的一个子女
min{ dfn[v] } // v与u邻接， 且（u，v）是一条回边
}
// File Name :poj1523.cpp
// Author :Freetion
// Created Time :2013年09月11日 星期三 22时40分42秒 #define LOCAL //Please annotate this line when you submit
/********************************************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#define CLE(name) memset(name, 0, sizeof(name))
using namespace std; const int max_n = ;
int edge[max_n][max_n]; //边的邻接矩阵
int vis[max_n];//顶点访问状态
int node; //记录最大的节点号
int tmpdfn; // 在dfs中记录当前深度优先数
int dfn[max_n]; // 记录每个顶点的深度优先数
int low[max_n]; // 记录每个顶点通过回边或邻边所能达到的最低深度优先数
int son; // 根的子女数
int subnet[max_n]; // 记录每个节点（去掉该节点后）的连通分量个数 //深度优先搜索，求每个节点的low值（根据low值判断是否为割点）
void dfs(int u)
{
for (int v = ; v <= node; v ++)
{
if (edge[u][v]) // 边存在
{
if (!vis[v]) // 没有被访问过，则v是u的儿子节点
{
vis[v] = ; //标记
dfn[v] = low[v] = ++ tmpdfn; //dfs值 和 初始的low值
dfs(v); // 递归
low[u] = min(low[u], low[v]); //求low的第二种情况
if (low[v] >= dfn[u])
{
if (u != )
subnet[u] ++;
else son ++;
//因为跟节点没有进入的边，只有出的边所以需要单独处理一下
}
}
else low[u] = min(low[u], dfn[v]); // 求low第三种情况的
}
}
} int main()
{
int i, u, v, find, num = ;
while (~scanf ("%d", &u) && u)
{
CLE(edge);
node = ;
scanf ("%d", &v);
if (u > node) node = u;
if (v > node) node = v;
edge[u][v] = edge[v][u] = ;
while (scanf ("%d", &u) && u)
{
scanf ("%d", &v);
if (u > node)
node = u;
if (v > node)
node = v;
edge[u][v] = edge[v][u] = ;//标记边存在
}
//以下是初始化
dfn[] = low[] = tmpdfn = ;
son = ;
CLE(vis); CLE(subnet);
vis[] = ;
//以上是初始化
dfs(); // 默认根节点为 1；
if (son > ) //单独处理根
subnet[] = son -;
find = ;
if (num > )
puts("");
printf ("Network #%d\n", num ++);
for (int i = ; i <= node; i ++)
{
if (subnet[i])
{
find = ;
printf (" SPF node %d leaves %d subnets\n", i, subnet[i] +);
//因为有一条入边所以还要加上一个 1；
}
}
if (find == )
printf (" No SPF nodes\n");
}
return ;
}