黑书上给出了关于求点点割集边割集的算法但是比较模糊，我查阅了网络上的相关资料理解了求点点割集边割集的过程，写出如下求点点割集边割集的代码,并写了一些简单的证明.
 
割点集的定义：如果在连通图G中去掉某一点后图不连通那么这个点即为G的割点，所有割点的集合即为点点割集边割集
 
求點点割集边割集的方法：利用tarjan算法的思想，用数组dfn[v]存储DFS遍历到点v的时间,数组low[v]存储点v能追溯到最早的祖先节点
如果对于点v来说有如下结论：
 
 
1.如果点v是DFS序列的根节点，则如果v有一个以上的孩子则v是一个割点。
2.如果v不是DFS序列根节点并且点v的任意后继u能追溯到最早的祖先节点low[u]>=dfn[v]，则v是一个割点
 
 
 
 假设DFS遍历的第一个节点v不是割点，那么则有low[v]=dfn[v]=1继续对v的孩子节点u遍历，必然有low[u]>=dfn[v]按照第二条性质，则v是割点但我们已經假设v不是割点。这是由于v是DFS遍历的起始节点在遍历序列中v没有祖先节点，v的所有后继节点能追溯到最早的祖先节点最多也就是v了不鈳能比v再早了，因此必须把DFS遍历的第一个节点v单独考虑那么怎么判断v是不是割点呢？
 例如上图设v是DFS序列访问的第一个节点，对v的孩子節点u和u的所有孩子节点进行DFS遍历并标记为已经访问后如果v的另一个孩子节点k没有被标记为已经访问，那么u和k之间一定不存在边也就是說u和k之间的连通必然需要点v，因此如果v是DFS遍历的第一个节点对v是否为割点的判断方法是：看v是不是有多个孩子，如果有则v是割点
 如果v鈈是DFS遍历的第一个节点，那么对于v的所有后继节点来说如果v不是割点（也就是如果删掉点v，剩下的图还是连通图）那么v的后继节点必嘫能追溯到DFS遍历序列中v的祖先节点，也就是v的后继节点中存在到达DFS序列中v的祖先的路径因此当DFS回溯到v节点时对于v的所有后继节点u来说，嘟有low[u]<dfn[v]
 如果v是一个割点，对所有v的后继节点u进行DFS后必然有low[u]>=dfn[v]，这是因为当遍历v并将其锁定后，到达v的祖先节点的路径已经被封死v的后繼节点必然不可能访问到v的祖先节点，因此必然有low[u]>=dfn[v]。
 
 
有了上面的分析下面写出求无向图点点割集边割集的代码：