无向图的强连通分量
2018-06-17 21:07:44来源:未知 阅读 ()
本篇博客存在非常大的概念上的错误(算法没有错误)
更正的版本在这里
http://www.cnblogs.com/zwfymqz/p/8480552.html
http://www.cnblogs.com/zwfymqz/p/8480429.html
对此,我表示深深地抱歉
在学习无向图的强联通分量之前
你首先要明白有向图的强联通分量
以前的自己too naive ,这玩意儿其实叫边双联通分量QWQ。。
定义
对于任意两个点,如果存在至少两条互相不重合的路径,使得这两点可以相互到达,那么这两个点就属于同一个强联通分量
比如说
在这张图中,
$1,2,3$属于一个强联通分量
$4$属于一个强联通分量,因为$3,4$只有一条可以相互到达的路径
实现
和有向图的强联通分量类似
都是用Tarjan算法实现
在求无向图的强联通分量重,我们不允许走已经走过的边
所以我们在Tarjan的过程中还需要记录一个father
走的时候只能走目标节点不是father的点
int Tarjan(int now,int fa)
{
dfn[now]=low[now]=++tot;
vis[now]=1;
s.push(now);
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(dfn[edge[i].v]==0)
Tarjan(edge[i].v,now),low[now]=min(low[now],low[edge[i].v]);
else if(vis[edge[i].v]&&edge[i].v!=fa)
low[now]=min(low[now],dfn[edge[i].v]);
}
if(dfn[now]==low[now])
{
int top;
++colornum;
do
{
top=s.top(); color[top]=colornum;
vis[top]=0; s.pop();
}while(top!=now);
}
}
例题
放一道我们考试的题目
题解点这里
向下翻到第三题
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 加边的无向图--并查集 2020-04-10
- 图的连通分量(利用邻接表存储信息) 2020-04-02
- 二值图像连通域标记算法优化 2020-03-11
- 割点 2019-08-26
- 图的两种存储结构及四种形态——邻接矩阵、邻接表;有向图、 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash