注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

双联通分量  

2015-03-15 19:46:49|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转自 http://www.haogongju.net/art/1330869

1:一些概念

割点:是无向连通图中一个顶点v, 如果删除它以及它关联的边后,得到的新图至少包含两个连通分支。

桥:无向连通图中的一条边,如果删除它,得到的新图包含两个连通分量。

双连通图:不含割点的无向连通图。

双连通分支:无向连通图的最大双连通子图。

点双连通分支:(自己猜的)通过找割点获得的双连通分支。

边双连通分支:(自猜)通过找桥获得的双连通分支。

举个例子:一个无向图有 1、2、3、4、5共5个顶点,一共有如下6条边,1 2,2 3,1 3,3 4,3 5,4 5,由于去掉任意一条边原图都是连通的,所以原图整体是边双连通的,但3是一个割点,如果去掉3原图就不连通了,所以原图整体不是点双连通的。还有是在有重边的情况下,边连通和点连通有点区别。

2:思路:tarjan算法

用dfs搜索整个图,用dfn[]记录节点搜索到的时间,low[]记录从该节点能够通过树边和反向边到达的最早搜索到的节点。(注意,这里的反向边(连接到dfs搜索树祖先的边)不考虑反向连接父亲的那条边,因为无向图的边会变成两个方向的边)

  对于强连通分量,对每个节点u DFS,遇到一个没有访问过的节点v即dfn[v] == 0,则继续递归搜索tarjan(v),之后重置low[u] = min(low[u], low[v]);如果遇到的是之前访问过的节点v(在栈中的,由于存在横插边,需要mark[]记录节点是否在栈中),则直接重置low[u] = min(low[u], dfn[v])。当节点u的所有儿子访问完成判断u节点是否为根节点(low[u] == dfn[u]),其表示u之后的节点不能通过后向边到达u之前,取出强连通分量则用栈存节点。

  要求双联通分支,先要知道割点和桥的求法。

3:割点和桥的求法

  割点的充要条件:在搜索过程中,对于边(u, v),如果u为树根,则若u有两个以上的儿子节点,则u为割点;如果dfn[u] <= low[v],则u为割点。(后来的程序里貌似直接在v未访问过的情况下判断dfn[u] <= low[v])

  桥的充要条件:对于边(u, v), 如果dfn[u] < low[v], 则(u, v)为桥(为什么不取’=’,见上面点边双连通所举得例子)。

  可以在一个程序中同时求割点和桥:

stack<int> s;
void tarjan(int x, int fa)
{
dfn[x] = low[x] = time++;
s.push(x);
for(int e = first[x]; e != -1; e = next[e])
{
if(dfn[v[e]] == 0)
{
tarjan(v[e], x);
if(low[x] > low[v[e]]) low[x] = low[v[e]];
else if(dfn[x] < low[v[e]])
{
//说明边e是桥
}
}
else if(v[e] != fa)
{
if(low[x] > dfn[v[e]]) low[x] = dfn[v[e]];
}
}
//在对该节点访问之后判断x是否为割点,如果要求出强联通则
//需要在循环内判断
if(dfn[x] == low[x])//u是根
{
//u 是割点 <=> u 有至少两个子节点
}
else //x 是割点 <=> x 有一个子节点v[e],满足d[x]<= low[v[e]]
}

4:点双连通和边双连通
  点双连通是在求割点的过程中把双连通分支求出来,每次将树边和反向边加入到栈中,如果遇到节点u存在节点v,使 dfn[u] <= low[v], 则找到一割点u,这时将边出栈,知道(u, v)出栈,得到的就是一个点双连通分支。由于无向图只存在树边和反向边,在循环的判断中可以通过这两这种边的特性来去除无向边的重复。树边表示v节点没有被访问,则dfn[v] == 0,即有dfn[v] < dfn[u];反向边也有dfn[v] < dfn[u]。所以用if(v != fa && dfn[v] < dfn[u]) 可以将反向连接父亲的边,树边的反边,和反向边的反边(后两个是dfn[u] > dfn[v])。

 

stack<int> s;
int num = 1;
int time = 0;
int id[1000] = {0};
void tarjan(int x, int fa)
{
dfn[x] = low[x] = time++;
for(int e = first[x]; e != -1; e = next[e])
{
if(x != fa && dfn[x] < dfn[v[e]])
{
s.push(e);
if(dfn[x] == 0)
{
tarjan(v[e], x);
if(low[v[e]] < low[x]) low[x] = low[v[e]];
if(low[v[e]] >= dfn[x])//x是割点
{
int edge;
do{
s.pop();
edge = s.top();
id[u[edge]] = id[v[edge]] = num++;
}while(u[edge] != x || v[edge] != v[e]);
}
}
else if(dfn[v[e]] < low[x]) low[x] = dfn[v[e]];//只剩下反向边了

}
}
}

  边双连通也是一样的过程,找到桥之后不断出栈。要注意的是桥的个数要比双连通数少1,最后节点无法全部出栈,借鉴网友的将num = 1开始,id[]置为0,则最后剩下的点被自然分成一个标号为0的双连通分量了。

void tarjan(int u,int fa)
{
int e;
dfn[u]=low[u]=++time;
s[top++]=u;
for(e=first[u];e!=-1;e=next[e])
if(v[e]!=fa)
{
if(!dfn[v[e]])
{
tarjan(v[e],u);
if(low[v[e]]<low[u])
low[u]=low[v[e]];
else if(low[v[e]]>dfn[u])
{
for(s[top]=-1;s[top]!=v[e];)
id[s[--top]]=num;
num++;
}
}
else if(dfn[v[e]]<low[u])
low[u]=dfn[v[e]];
}
}
  评论这张
 
阅读(5499)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018