割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。 直观地说，就是删除了连通图的某点后，图不在连通，而是分为几个连通分量。
性质：（1）考虑根节点Root，如果Root有数量多于1的子结点时，Root是割点。
（2）考虑非根结点u，当且仅当u的某个儿子及儿子的子孙均没有指向u的祖先的后向边时，u是割点。（LOW[v]>=DFN[u],v是u的孩子）
代码：
1 void DFS( int cur, int par) 2 { 3 dfn[cur] = low[cur] =++ Index; 4 5 int size = adj[cur].size(); 6 int cnt = 0 ; 7 for ( int i = 0 ;i < size;i ++ ) 8 { 9 int v = adj[cur][i]; 10 if ( ! dfn[v]) 11 { 12 cnt ++ ; 13 DFS(v,cur); 14 if (low[cur] > low[v]) 15 low[cur] = low[v]; 16 if ((cur == root && cnt == 2 ) || (cur != root && low[v] >= dfn[cur])) 17 flag[cur] = true ; 18 } 19 else if (v != par && low[cur] > dfn[v]) 20 low[cur] = dfn[v]; 21 } 22 } 23
割边：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。
性质: 对于一条边<u,v>，v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时，<u,v>是割边。（LOW[v]>DFN[u]）
代码：
1 void CutEdge( int cur, int par) 2 { dfn[cur] = low[cur] =++ Index; 3 4 for ( int i = head[cur];i;i = buf[i].next) 5 { 6 int v = buf[i].v; 7 if (v == par) continue ; 8 if ( ! dfn[v]) 9 { 10 CutEdge(v,cur); 11 if (low[cur] > low[v]) 12 low[cur] = low[v]; 13 if (low[v] > dfn[cur]) 14 { 15 ans[nAns ++ ] = buf[i].id; 16 } 17 } 18 else if (low[cur] > dfn[v]) 19 low[cur] = dfn[v]; 20 } 21 }
相关习题：
POJ 1144 Network 赤果果的求割点的题。
相关链接:Beyond the Void的讲解，很精彩
推荐阅读：
lrj的黑书P285
