- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
完结篇:tarjan 求割点、点双连通分量、割边(桥)(附 40 道很好的 tarjan 题目).
上一篇(tarjan 求强连通分量,缩点,求边双) 。
还是求强联通分量的大致思路捏. 。
我们把图中的点分为两种: 每一个联通子图搜索开始的根节点 和 其他点.
判断是不是割点的方式如下:
对于根节点: 记一下在跑 tarjan 过程中从这个点出发的未被搜索到的子节点的数量 \(child\),如果 \(child\ge 2\),那么这个点为割点,否则就不是割点; 。
设根节点为点 \(u\),如果 \(child\) 为 1 的话,说明根节点的不同子树上的点可以不经过点 \(u\) 而互相到达,也就是说即使删了 \(u\) 点,图中所有点照样可以互相到达,则 \(u\) 不为割点。反之,同样也易证得为割点.
对于其他点: 判断一个点 \(u\) 有没有一个子节点 \(v\) 使得 low[v] >= dfn[u],若存在,则 \(u\) 为割点,否则不为割点.
因为我们在无向图中跑 tarjan 时,已经特判父节点或边的编号来避免走“回头路”了(详见上文求边双部分),所以如果满足判断条件时,说明 \(v\) 通过返祖边只能到达 \(u\) 及其子树部分,并不能到达 \(u\) 的祖先节点,所以若 \(u\) 点删去,那么 \(v\) 点便与 \(u\) 以上部分断开了,此时显然 \(u\) 为割点.
会判断这两类点是不是割点之后就做完了,相信大家也知道该怎么求了。看代码吧! 。
相比于求边双部分增加了数组 cut[x] 来判断 \(x\) 是不是割点,若为 true 则 \(x\) 是割点,否则不是.
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x; int child = 0;
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x]){
child++;
if(p != 0 or child > 1) cut[x] = 1;
}
}
else low[x] = min(low[x], dfn[y]);
}
}
为什么 p == 0 说明 \(x\) 为根节点呢,大家肯定知道啦! 。
因为主函数中是这么写的:
for(int i=1; i<=n; i++)
if(!dfn[i]) tarjan(i, 0);
我该先写求点双好呢还是先写求割边好呢,这俩都是需要割点的相关知识的,啊选择困难症( 。
但是的但是,学会求割点之后那求点双(简称 BCC)就很简单啦 啦啦小魔仙,玛卡巴卡,卡巴露露,摇身变! 。
性质:无向连通图中割点一定属于至少两个BCC,非割点只属于一个BCC 。
如此图:2 号点是个割点,其他点则不是。有红、蓝两个 BCC.
有一条显然的结论:每个点双,它在 dfs 时最先被发现的点一定是割点或者 dfs 树的树根.
证明:这很显然吧?!根据割点的定义自己理解一下,不证明。算了,还是简单说一下吧:我们知道割点是 BCC 的交点,即 BCC 通过割点连接,从一个 BCC 到另一个 BCC 一定是从经过割点开始的,所以证得.
那么这条结论其实就等价于 每个 BCC 都在其最先被发现的点(一个割点或根节点)的子树中。那么我们在上文求割点方法基础上每找到一个割点(或根节点)后,其子树(包含自己)便是一个点双连通分量了.
我们还是维护一个栈,存点,每当搜索到一个点时就将该点入栈,找到割点(就是找到一个 BCC)时将栈顶到该割点所有元素依次出栈,(但注意:割点并不出栈,因为上文已说一个割点属于两个 BCC,它还需要来更新另一个 BCC,所以先不出栈,特判就行。)那么出栈的元素以及割点就是所求的点双了.
如上图中,我们以 1 为根开始搜索; 。
搜索到 2 节点时,继续递归 2 -> 3 -> 4;发现 \(low_4 = 2 < dfn_3\),那么 3 号点则不是割点,回溯; 。
而 \(low_3 = dfn_2\),所以 \(2\) 号点是割点,那么将此时栈中从栈顶到 \(2\) 号点所有元素出栈形成点双; 。
此时栈从栈尾到栈顶依次是:1,2,3,4。那么便是 2,3,4 构成一个点双(但 2 还在栈中).
继续回溯到 2 -> 1;发现 1 号点是根节点,也将栈中元素出栈(这时 1 是根节点,所以 1 也出栈),那么 1,2 就又构成了一个点双.
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x;
if(!p and !head[x]){ // 特判孤点
BCC[++bcc].emplace_back(x);
top--; return;
}
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x] or !p){ //是割点或者根节点
++bcc;
do BCC[bcc].emplace_back(s[top]);
while(s[top--] != y);
BCC[bcc].emplace_back(x);
}
}
else low[x] = min(low[x], dfn[y]);
}
}
板子题练练手。注意这题需要判孤点情况.
太简单啦! 。
和割点差不多,改一条:low[y] > dfn[x],并且不需要特判根节点了(因为 边 != 点).
解释:(在判边保证不走回头路的条件下)\(low_y = dfn_x\) 时,说明不通过从 \(x -> y\) 这条路径, \(y\) 也照样可以回到 \(x\) 节点,那么就保证从 \(y\) 到 \(x\) 有两条路径可走了,所以 \(x->y\) 这条路不是割边.
那么完了! 。
cut[i] = true; 表示 \(i\) 这条路为割边.
void tarjan(int x, int p){
low[x] = dfn[x] = ++th;
s[++top] = x;
for(int i=head[x]; i; i=nxt[i]){
int y = to[i];
if(y == p) continue;
if(!dfn[y]){
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x]){
cut[i] = true;
}
}
else low[x] = min(low[x], dfn[y]);
}
}
这有个很好的 tarjan 题单,从模板到进阶,题都很好,推荐给大家.
P1656 炸铁路
P1455 搭配购买
P3916 图的遍历
P2835 刻录光盘
P1073 [NOIP2009 提高组] 最优贸易
P2863 [USACO06JAN]The Cow Prom S
P8436 【模板】边双连通分量
P8287 「DAOI R1」Flame
P2002 消息扩散
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
P3387 【模板】缩点
P3388 【模板】割点(割顶)
P8435 【模板】点双连通分量
P1407 [国家集训队]稳定婚姻
P2194 HXY烧情侣
P2746 [USACO5.3]校园网Network of Schools
P2812 校园网络【[USACO]Network of Schools加强版】
P2941 [USACO09FEB]Surround the Islands S
P2860 [USACO06JAN]Redundant Paths G
P3398 仓鼠找 sugar
P2169 正则表达式
P3627 [APIO2009] 抢掠计划
P2656 采蘑菇
P4306 [JSOI2010]连通数
P5676 [GZOI2017]小z玩游戏
P1656 炸铁路
P1455 搭配购买
P3916 图的遍历
P2835 刻录光盘
P1073 [NOIP2009 提高组] 最优贸易
P2863 [USACO06JAN]The Cow Prom S
P8436 【模板】边双连通分量
P8287 「DAOI R1」Flame
P2002 消息扩散
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
P3387 【模板】缩点
P3388 【模板】割点(割顶)
P8435 【模板】点双连通分量
P1407 [国家集训队]稳定婚姻
P2194 HXY烧情侣
P2746 [USACO5.3]校园网Network of Schools
P2812 校园网络【[USACO]Network of Schools加强版】
P2941 [USACO09FEB]Surround the Islands S
P2860 [USACO06JAN]Redundant Paths G
P3398 仓鼠找 sugar
P1262 间谍网络
P4742 [Wind Festival]Running In The Sky
P8867 [NOIP2022] 建造军营
P3469 [POI2008]BLO-Blockade
P2515 [HAOI2010]软件安装
P5058 [ZJOI2004]嗅探器
P7687 [CEOI2005] Critical Network Lines
P7924 「EVOI-RD2」旅行家
P5236 【模板】静态仙人掌
P3225 [HNOI2012]矿场搭建
P4716 【模板】最小树形图
P4126 [AHOI2009]最小割
P6335 [COCI2007-2008#1] STAZA
P4637 [SHOI2011]扫雷机器人
P5236 【模板】静态仙人掌
P4716 【模板】最小树形图
P4436 [HNOI/AHOI2018]游戏
历时多天,终于把这两篇 tarjan 写完了.
tarjan 都学了,那下一章包得是圆方树的啦( 。
\(敬请期待......\) 。
最后此篇关于一文轻松搞定tarjan算法(二)(附带tarjan题单)的文章就讲到这里了,如果你想了解更多关于一文轻松搞定tarjan算法(二)(附带tarjan题单)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
滑动窗口限流 滑动窗口限流是一种常用的限流算法,通过维护一个固定大小的窗口,在单位时间内允许通过的请求次数不超过设定的阈值。具体来说,滑动窗口限流算法通常包括以下几个步骤: 初始化:设置窗口
表达式求值:一个只有+,-,*,/的表达式,没有括号 一种神奇的做法:使用数组存储数字和运算符,先把优先级别高的乘法和除法计算出来,再计算加法和减法 int GetVal(string s){
【算法】前缀和 题目 先来看一道题目:(前缀和模板题) 已知一个数组A[],现在想要求出其中一些数字的和。 输入格式: 先是整数N,M,表示一共有N个数字,有M组询问 接下来有N个数,表示A[1]..
1.前序遍历 根-左-右的顺序遍历,可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
先看题目 物品不能分隔,必须全部取走或者留下,因此称为01背包 (只有不取和取两种状态) 看第一个样例 我们需要把4个物品装入一个容量为10的背包 我们可以简化问题,从小到大入手分析 weightva
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件,该帐户已经打开并记录,但真的不知道从哪里开始(对于 outlook-c++ 集成),谷歌也没有帮我这么多。任何提示将不胜感激。
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后,代码运行另一个命令。 代码如下: #include "cv.h" #include "cxcore.h" #include "high
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。 我想在矩阵中指定一个起点,并像 imfill 的 4 连接版本那样进行洪水填充。 这是否已经存在于
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录,如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
我遇到了一个问题,但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点,但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值,那么我会得到一个列表 L2。我有另一个列表 L3,它是 L2 的某个
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2,因为4+4=8 >= 7,
我实行 3 类倒制,每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单,即它永远不会改变,即使那个星期不工作也是如此。 我创建了一个函数来获取 ISO 周数。当我给它一个日期时
假设我们有一个输入,它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合,可能包含这些元素的任意组合,也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
我有一个子集算法,可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合,如果向其中添加元素,我需要再次重新计算它的子集。 有没有一种方法可以优化子集算法,该算法可以从最后一个计算点重新
我有一个包含 100 万个符号及其预期频率的表格。 我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列,然后将它们连接在一起以表示序列。 我想分配这些位串,以使编码序列的预
我是一名优秀的程序员,十分优秀!