题目链接：
?id=1523
题目大意：
所示：如果3号电脑出故障了，那么1号和2号之间、4号和5号之间还可以通信，不过1、2和3、4
号电脑之间就不能通信了，那么3号电脑就是一个SPF节点，且3号电脑故障后，整个网络被分为
了2个子网络。那么问题来了：给你一些边。问删除某个SPF节点后，可以将图分为几个连通分量。
思路：
其实就是给你一个连通图，求出这个连通图的所有割点编号，并求出若删去其中一个割点后，原网
络被分成几个子网络。这里我们使用的思路和Tarjan算法类似。
(1)对原图进行深度优先搜索，计算树上每一个节点v的搜索深度标号dfn[v]。
(2)计算所有节点v的low[v]是在深度优先搜索树上按照后根遍历的顺序进行的。所以，当访问节点v
时它的儿子u的low[u]已经计算完毕，这时low[v]取下面三个值中的最小值。1.dfn[v]、2.dfn[w](凡
是含有回退边(v，w)的任何节点w)、3.low[u](对v的任何儿子u)
(3)然后判断一个点是不是割点，如果一个节点v是割点，满足下面两种情况。
1.v为树根，且v有多于一个子树；2.v不为树根，且满足存在边(v，u)，使得dfn[v] <= low[u]。
注：我在程序中定义son[v]为节点v的深度，深度优先搜索时，每入栈一次，son[v]+1，，每退栈一次，
son[v]-1。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 1010;const int MAXM = MAXN*MAXN;struct EdgeNode{int to;int next;}Edges[MAXM];int Head[MAXN];int dfn[MAXN],low[MAXN],Stack[MAXN],son[MAXN];int m,id,scc,lay,N;void AddEdges(int u,int v){Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;}void TarjanBFS(int pos,int from){Stack[m++] = pos;dfn[pos] = low[pos] = ++lay;for(int i = Head[pos]; i != -1; i = Edges[i].next){if(Edges[i].to == from)continue;if( !dfn[Edges[i].to]){TarjanBFS(Edges[i].to,pos);low[pos] = min(low[pos],low[Edges[i].to]);if( dfn[pos] <= low[Edges[i].to] ){while(Stack[m–] != Edges[i].to);son[pos]++;}}elselow[pos] = min(low[pos],low[Edges[i].to]);}}int main(){int u,v,kase = 0;while(~scanf("%d",&u) && u){N = -1;m = lay = scc = id = 0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(son,0,sizeof(son));memset(Head,-1,sizeof(Head));N = max(N,u);scanf("%d",&v);N = max(N,v);AddEdges(u,v);AddEdges(v,u);while(scanf("%d",&u) && u){N = max(N,u);scanf("%d",&v);N = max(N,v);AddEdges(u,v);AddEdges(v,u);}printf("Network #%d\n",++kase);TarjanBFS(1,0);son[1]–;int flag = 0;for(int i = 1; i <= N; ++i){if(son[i] > 0){printf(" SPF node %d leaves %d subnets\n", i, son[i]+1);flag = 1;}}if(flag == 0)printf(" No SPF nodes\n");printf("\n");}return 0;}
而开始追寻他内心世界的真正财富
