企业网站的综合要求,互联网时代的营销,怎么样分析一个网站,龙海市城乡规划建设局网站文章目录 前言割点定义割点的求解割点判定定理证明#xff08;非严谨#xff09; 算法实现算法流程代码详解 再看SCCOJ练习 前言 之前介绍Tarjan算法求强连通分量时#xff0c;提到了代码段中对于访问过的邻接点应用其时间戳来更新追溯值#xff0c;不是说用追溯值更新会导… 文章目录 前言割点定义割点的求解割点判定定理证明非严谨 算法实现算法流程代码详解 再看SCCOJ练习 前言 之前介绍Tarjan算法求强连通分量时提到了代码段中对于访问过的邻接点应用其时间戳来更新追溯值不是说用追溯值更新会导致答案错误而是为了和后续双连通分量的代码保持统一。学习双连通分量求解要先了解割点个割边的概念本文来介绍割点。 关于Tarjan算法求解强连通分量见SCC-Tarjan算法强连通分量算法从dfs到Tarjan详解-CSDN博客 割点定义
在一个无向图中如果将一个点及与该点相连的边删除后连通分量会被断开分为 2 个及以上这个点就是一个割点也称割顶。
割点的求解
割点的定义十分简洁其求解思路也十分简单同样是基于Tarjan-SCC算法详见。
割点判定定理
如果x不是根节点当搜索树上注意条件为搜索树上存在x的一个子节点y满足low[y] ≥ dfn[x]那么x就是割点。如果x是根节点即连通分量中最早访问节点当搜索树上存在至少两个子节点y1y2满足上述条件那么x就是割点。
在证明之前我们先通过下面例子来理解一下 为了方便说明我们给的示例中点的编号与dfn值相同旁边标注的是low值
**对于定理1**定理1用于判定非根割点对于示例我们观察节点5其邻接点low值均不小于5我们发现割掉5后原本的连通分量{12345678}变为了{1234}、{6}和{78}
**对于定理2**定理1用于判定根割点那我们直接看根1我们发现245均满足此时满足条件的邻接点数目大于1我们删掉1后得到了{234}和{5678} 证明非严谨
定理1
对于非根节点x当搜索树上注意是搜索树上而非原图上存在x的一个子节点y满足low[y] ≥ dfn[x]那么说明子节点y在不通过x的情况下是无法抵达比x时间戳更早的节点的这也就说明了x是所在环的环顶否则如果不是环顶那么y一定可以通过环顶到达更早时间戳。
那么由于环顶x非根所以x和环外节点有边连接割掉x后必然能够多分出至少一个连通分支。
定理2
先说明为什么搜索树上x只有一个子节点满足条件不是割点。
由于根节点只跟自己连通分量内节点有边与其他连通分量的点无边当割掉根x那么对于原连通分量来说并不会分为多个连通分量因为原来根x的唯一满足条件的子节点y会成为新的根因为除了y的其它子节点一定可以抵达y它们仍是一个连通分量。
那如果至少有两个子节点我们不妨设为yz满足呢
那么对于yz而言它们不通过x的情况下彼此互相不可达即处于两个环否则搜索过程中二者时间戳早的那个一定可以访问晚的那个这样就不存在y、z都满足条件了。
那么割掉x后x所在环和y所在环由于失去x而互相不可达分为了两个连通分量当满足条件的子节点大于2时则会更多。
我们以下图为例 我们观察右图搜索树发现1只有2一个子节点割掉1后仍为一个连通分量。 算法实现
求解割点算法实现十分简单我们要判定搜索树上节点的子节点即我们深搜过程中访问子节点过程中还未访问的子节点我们只要在这个过程中进行割点判断即可。
算法流程
对x深搜打时间戳访问子节点yy未访问则对y深搜更新low[x] 如果low[y] low[x]若x不是根那么x为割点否则符合条件子节点数目child1如果child1x为割点 y已访问更新low[x]
代码详解
#define N 20010
#define M 200100
//链式前向星
struct edge
{int v, nxt;
} edges[M];
int head[N]{0}, idx 0;
void addedge(int u, int v)
{edges[idx] {v, head[u]};head[u] idx;
}int dfn[N]{0}, low[N]{0}, tot 0, root;
// dfn 时间戳 low节点所能访问的最小时间戳 tot为访问节点的时间戳编号
bitsetN cut;//cut标记数组void tarjan(int x)
{dfn[x] low[x] tot;int y, child 0;for (int j head[x]; ~j; j edges[j].nxt){y edges[j].v;if (!dfn[y])//搜索树上子节点{tarjan(y);low[x] min(low[x], low[y]);if (low[y] dfn[x]){child;if (x ! root || child 1)cut[x] 1;}}else{low[x] min(low[x], dfn[y]);}}
}再看SCC
此时对于割点代码段中else语句“low[x] min(low[x], dfn[y]);”应该理解为什么用父节点dfn值更新而非low值了如果用low值说明子节点可以越过父节点到达更早节点这显然是不合理的如下图 那么我们SCC算法中用low[x] min(low[x], dfn[y])是否会影响SCC算法正确性呢自然不会不然你OJ怎么过的因为这不会影响我们根的判定而且也不会影响从栈中获取SCC内的节点。
到这里对于Tarjan求SCC应该就再无疑惑了。
OJ练习
P3388 【模板】割点割顶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
