POJ 1523 SPF Tarjan求割点

链接：http://poj.org/problem id=1523

题意：N台电脑，如果某台坏掉了，其他电脑就会分成几个不相连接的部分。找出这些电脑，并且算出其坏了其他电脑会分成几个部分。

思路：Tarjan算法求割点。模板来源自刘汝佳白书。

相关资料：（以下转载，源头不可考）

无向连通图的割点与割边：

最简单的方法：要判断一个点是否为割点，先把这个点和所有和它连接的边从图中去掉，再遍历下剩余的图，看看是否为连通的即可。这只在单独判断某一点(边)时才会选用。

时间复杂度O(n2)。

割点将一个图分成了两部分，设从任一部分的任一点出发对图进行DFS遍历，当遍历递归到割点后，就进入了图的第二部分。又因为每个点只能visit一次，所以第二部分的点不论怎样遍历再也回不到第一部分了。当所有点(第二部分中)都被访问完后，才回溯到割点，再继续向上回溯。

在DFS的过程中，记录每个点u在DFS树中的标号n1(放在dep[u]中)，以及该点所能到达的最小顺序号n2(存在low[u]中)。注意：这个n2在求取时，是递归进行的，从u的子孙们的low值n2与u的祖先们的dep值n1(此时u祖先的low值还未求出，dep相当于它的low值)中挑出最小的。这就给了u的儿子们low值比u还小的机会。然而，如果u是割点，那么u孩子们的low值就决然 >= u 了。这也就成了判断u是割点的方法。

至于割边，可以再判断u是否为割点的同时，顺便判断 是否为割边。只要满足low[i]>u就行了。

另外，对于dfs起点就是一个割点的情况：如果不是割点，那它必然只有一个儿子(其他连接都被dfs回溯掉了)。它必须是割点，才能保证它的几个儿子不被dfs回溯掉。

注意：想要记录割点u切去后增加的连通分量数目。不能简单的记录u的孩子数，而必须在判断u为割点成立的地方进行统计。即有多少个证明了u是割点的孩子，它们就是u在切除后生成的新连通分量。割点u的某些孩子不一定能证明u是割点，因为它可能与比u小的某个点相连，从而使自己的low值比u还小，这与具体的dfs树有关，即遍历的顺序有关。 可见末尾的一组数据，对同一个图的描述，由于建树的方式不同，导致3的儿子4，不能证明3是割点。从而使3的孩子数(3) ！= 3造就的连通分量数2（删除3后，两棵子树成为连通分量）。

针对这点再强调一点：对根节点删掉自己后，就只剩新生的联通分量了。不同于枝节点，还有旧的连通分量在。

汇总如下：
如果根结点有大于1个的儿子，那么根结点是割点。
如果对于点u的某个儿子v，有low[v] >= dep[u]，那么u就是一个割点。
如果对于点u的某个儿子v，有low[v] > dep[u]，那么(u,v)是一条割边。

（转载结束）

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include