
Tarjan算法(模板)
发布日期:2021-05-06 14:13:04
浏览次数:13
分类:技术文章
本文共 1250 字,大约阅读时间需要 4 分钟。
算法思想: 首先要明确强连通图的概念,一个有向图中,任意两个点互相可以到达;什么是强连通分量?有向图的极大连通子图叫强连通分量。
给一个有向图,我们用Tarjan算法把这个图的子图(在这个子图内,任意两个点可以相互到达,极大的子图)缩成一个点,相当于化简; 怎样去做:从一个点开始遍历它能走到的下一个点(dfn记录时间戳,low记录能回到的最早的时间戳),每遍历到一个点,判断这个点如果没有走过(dfn值为零),继续深搜,如果走过了并且在栈里面说明可以形成一个环(那就可以缩成一个点,更新当前点low的值,回到更早的时间戳),搜完它可以到达所有的点以后回溯,更新low;直到回到 low[u]==dfn[u](环的“根节点"),出栈这个点上面的所有的点(包括这个点本身,他们可以缩成一个点).继续回溯. 特别注意:else if(instack[v])/*走过并且形成一个环??????*/ low[u]=min(low[u],dfn[v]);/*更新最小值low,合并集合*/ /*不能写成low[u]=min(low[v],low[u])*/
当计算有多少个强连通分量的时候,写成那个没关系,但是如果是求割点,两个语句求出来的low值不一样,值会偏小,割点判断错误(因为判断条件是if(low[v]>=dfn[u]))。
扩展: 计算出入度,问加多少条边可以变成一个整个连通分量: 在这里首先缩点,用一个color[ ]数组,将同一集合的点标记成某个序号(出栈的时候就是同一集合),最后遍历输入的边,用两个数组标记每一个集合的出度入度情况,得出入度和出度分别有几个集合为零,输出最大值。注意:调用tarjan函数的时候,用for循环,因为图可能不连通!还有当它本来就是一个连通分量的时候,特判一下。 例题:POJ 1236 Network of Schools#include#include #include #include #include #include using namespace std;#define N 1010vector edge[N];vector belong[N];stack s;int low[N];/*所属的强连通数组*/int dfn[N];/*访问的顺序*/bool instack[N];/*是否在栈内*/int n,m,u,v,cnt,cntb;/*n个顶点,m条边*/void Tarjan(int u)/*当前处于的节点*/{ ++cnt;/*计算访问到第几个点(时间戳)*/ dfn[u]=low[u]=cnt;/*访问的顺序(时间戳),low数组记录这个点所能回到的最早的时间戳*/ s.push(u); instack[u]=true; for(int i=0;i
发表评论
最新留言
很好
[***.229.124.182]2025年03月09日 03时49分29秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
实用网站推荐
2019-03-03
idea中写mybatis报错
2019-03-03
RestFul 风格
2019-03-03
CSS浮动属性
2019-03-03
HTML+CSS基础
2019-03-03
SVM多类识别
2019-03-03
LBP局部二值模式研究(待完善)
2019-03-03
Failed to load OpenCL runtime解决
2019-03-03
svn 撤销已提交的错误修改
2019-03-03
算法工程师数学理论提高札记(improving)
2019-03-03
CLRS 22.3-2,7 邻接表实现
2019-03-03
仿微信--主要版本说明
2019-03-03
Android存储
2019-03-03
Retrofit学习
2019-03-03
Android启动优化--AOP获取方法耗时
2019-03-03
Android卡顿优化--界面秒开
2019-03-03
Android网络优化--工具
2019-03-03
Android网络优化--精准获取流量消耗
2019-03-03
Android进程的启动流程
2019-03-03