割点

割点：如果在图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的孩子）

代码：

void DFS(int cur,int par)
 {
     dfn[cur]=low[cur]=++Index;
     
     int size=adj[cur].size();
     int cnt=0;
     for(int i=0;i<size;i++)
     {    
         int v=adj[cur][i];
         if(!dfn[v])
         {
             cnt++;
             DFS(v,cur);
             if(low[cur]>low[v])
                 low[cur]=low[v];
             if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
                 flag[cur]=true;
         }
         else if(v!=par&&low[cur]>dfn[v])
             low[cur]=dfn[v];
     }
 }
 

割边

割边：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。

 性质: 对于一条边<u,v>，v是u的孩子如果儿子及儿子的子孙均没有指向u的祖先的后向边时，<u,v>是割边。（LOW[v]>DFN[u]）

代码：

void CutEdge(int cur,int par)
 {    dfn[cur]=low[cur]=++Index;
     
      for(int i=head[cur];i;i=buf[i].next)
     {
         int v=buf[i].v;
         if(v==par)continue;
         if(!dfn[v])
         {
             CutEdge(v,cur);
             if(low[cur]>low[v])
                 low[cur]=low[v];
             if(low[v]>dfn[cur])
             {    
                     ans[nAns++]=buf[i].id;
             }
         }
         else if(low[cur]>dfn[v])
             low[cur]=dfn[v];
     }
 }

相关习题：

POJ 1144 Network 赤果果的求割点的题。

相关链接:
Beyond the Void的讲解，很精彩

推荐阅读：

lrj的黑书P285

• 相关文章