图的割点与割边学习笔记

割点

割点:如果在图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

posted on 2010-08-30 14:59 ZAKIR 阅读(2536) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年6月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜