割点/割边
1.定义：
对于一个无向图，
如果删除一个点，可以让一个图的连通分支数增加。那么这个点就是割点，
同样的，对于一条边，删掉之后可以让一个图的连通分支数增加，那么这条边就是割边。
2.关键的性质：
对于一条在连通图G中的割边e，一定存在这样的性质：
e不在G中的任意一个圈上。
如果我们对一个连通的无向图进行dfs，那么我们就会得到一颗dfs树
这是有了这样的两个定理：
第一， 根节点u是割点，当且仅当，u有两个及两个以上的子树。
就是它把多个子树分隔开。注意这里说的是子树，子树是互不连通的。
第二，非根节点u是割点，当且仅当，后代v都不可以通过回退边回到u的祖先w
如果v可以通过回退边回到w会发生什么？
显然这样会形成一个圈。如下图
显然，图中的u不是割点。因为v可以返回到u的祖先 w。
但是对于w而言呢？后代u和v都不可以返回到w的祖先s，所以w是割点。
讨论完了割点，我们来看看割边。
圈上的边一定不是割边
这是很显然的。如果u到v之间有圈，那么一定至少会有两条(u,v)，任意删除一条边都不会改变连通性。
3.割点算法的描述：
在dfs中，每一个点有两个数据：
dfn记录访问的时间点，也就是时间戳
low记录的是 可以回溯到的最早祖先的时间戳
之前我们讨论了，对于每一个节点的而言，我们需要分两个情况讨论。根与非根。
对于根来说我们只需要记录后代子树的个数就行了。
那么如何处理非根的情况呢。
只需要u的后代结点v满足：
low[v] >= dfn[u].
也就是说，v可以回溯到的最早的节点low[v]
仍然在u之下。
当然这里有两种情况，后向边和横叉边。
后向边：
这就像是，一根绳子上，一边是一个圈，另一边是另一个圈，割掉绳子上的任意一个点，就会使两个物体分开。那么很显然绳子上的每一个都是割点。
横叉边：
如果是横叉边我们发现这一定会回溯到根节点，这是一定会比dfn[u]小的，也就是说这是不可能的。
现在我们已经有了求割点的算法了：
dfs(int u){
for:each v of u{
if(v not visted){
dfs(v)
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]){
child++;
if(u is not root)
u is cut;
else if(child > 1)
u is cut;
}
}
else low[u] = min(low[u],dfn[v]);
}
}
4.割边算法的描述：
在已经得到了割点算法的同时我们来看看割边算法。在上述的讨论中我们发现，割边算法和割点算法是类似的。
横叉边一定会形成环，也就是一定会回溯到根。
后向边与割点是相同，但是不需要特判一个根。
正常的判断，也只需要将 low[v] >= dfn[u],改为low[v]>dfn[u]这就得到了我们的割边(u,v)。这是因为我们得到的(u,v)一定不是圈上的边，当取等号时，可以发现此时的(u,v)仍然在圈上。但是此时u确是割点。