图的割顶与桥
图的割顶即删掉之后图就不连通的顶点，桥即删掉之后图就不连通的边。
求图的割顶与桥都需要对图的DFS进行简单扩充，即在DFS过程中求出每个顶点的Low值，Low的定义是：
Low[v]=min{
Num[v],
Num[w], ( link[v][w] && Num[w] < Num[v] && Par[v]!=w ， 后向边)
Low[w], ( link[v][w] && Num[w] > Num[v] ，树边)
}
其中Num[v]表示每次DFS到v顶点时标记的时间戳，Par[v]是DFS树中v的父节点。
(v,w)是桥当且仅当Num[v]<Low[w]。
v是割顶当且仅当v不是根且Num[v]<=Low[w]或v是根且DFS树中v有不止一个的子节点。
（以上Par[w]==v）
示例程序（求图的桥）：
zju2588.cpp
Related posts
原文有些不妥，不知是不是笔误，应该这样说吧：
v是割顶当且仅当v不是根且存在w（Par[w]==v）使Num[v]
。。。丢一半。。。不过后边是一样的。。。
我括号里不是写有：以上Par[w]==v 么。
…我说的是
w是割顶当且仅当v不是根且Num[v]
^
v是割顶当且仅当v不是根且存在w使Num[v]
^ ^^^^^
也就是说，v是否为割顶，与v的儿子有关，而与父亲无关。
我是否说清楚了？
哎呀……笔误笔误，太谢谢你了。
不客气，还有一件事，我很想要你qq号啊。。。
如果可以就发到我邮箱吧，谢啦！
…hsiayh@163.com
2008-07-15 ×ܽá…
×òÌìÆäʵûÓÐ×öʲôºÃÌ⣬µ«ÊÇÕâ´ÎPKU±ÈÈüʹÎÒ´ÓÇ°¼¸ÌìµÄµÍÃÔ״̬Öлָ´Á˹ýÀ´¡£ÓÖÓÐÁË×öÌâµÄÓûÍûÁË£¬Ó¦¸ÃËãÊǺܼ°Ê±µÄ°É¡£Õâ´ÎPKU±ÈÈüµÄÌ…
怎么我的trackback还乱码了……