这道题的大意就是求割点，并且求出假如去掉这个割点后，整个图被分为了几部分
看的北大那本图论书，无向图的点连通性的求解。
然后就把代码打上来了。
书上是用邻接矩阵存储，我改用了vector
并且书上的代码也有一些问题，就是没有处理好边和回边的问题
因为low数组的定义，就是low[u] = min(dfn[u], low[w], dfn[v])
其中w是u的子女，而(u,v)是一条回边
所以在DFS的过程中，加入一个变量father,用来判断是否是回边，不是回边的话，显然是不能进行处理的
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
using namespace std;
vector<int>edge[1005];
int visited[1005];
int nodes;
int tmpdfn;
int dfn[1005];
int low[1005];
int son;
int subnets[1005];
void dfs(int u, int father)
{int x = edge[u].size();for(int i = 0; i < x; i++){int v = edge[u][i];if(!visited[v]){visited[v] = 1;tmpdfn++;dfn[v] = low[v] = tmpdfn;dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){if(u != 1)subnets[u]++;if(u == 1)son++;}}else if(v != father) low[u] = min(low[u], dfn[v]);}
}
void init()
{low[1] = dfn[1] = 1;tmpdfn = 1;son = 0;memset(visited, 0, sizeof(visited));visited[1] = 1;memset(subnets, 0, sizeof(subnets));
}
int main()
{int u, v, flag, cas = 0;while(scanf("%d", &u) != EOF && u){for(int i = 0; i <= 1000; i++)edge[i].clear();nodes = 0;scanf("%d", &v);if(u > nodes) nodes = u;if(v > nodes) nodes = v;edge[u].push_back(v);edge[v].push_back(u);while(scanf("%d", &u) != EOF && u){scanf("%d", &v);if(u > nodes) nodes = u;if(v > nodes) nodes = v;edge[u].push_back(v);edge[v].push_back(u);}if(cas) printf("\n");printf("Network #%d\n", ++cas);init();dfs(1, 0);if(son > 1) subnets[1] = son - 1;flag = 0;for(int i = 1; i <= nodes; i++){if(subnets[i]){flag = 1;printf(" SPF node %d leaves %d subnets\n", i, subnets[i] + 1);}}if(!flag)printf(" No SPF nodes\n");}return 0;
}