首页 > 其他分享 >【笔记/模板】割点和桥

【笔记/模板】割点和桥

时间:2024-11-04 10:44:41浏览次数:2  
标签:ver min 割点 笔记 dfn low 节点 模板

割点

对于一张无向图 \(G=(V,E)\),使得 H 是 G 的连通子图,且不存在 \(F\) 满足 \(H \subsetneq F \in G\) 且 \(F\) 为连通图,则称 \(H\) 是 \(G\) 的一个连通块/连通分量connected component),又叫极大连通子图

由此,我们可以对割点做出如下定义:

对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。

Tarjan

处理过程

与有向图的强连通分量相似,我们定义如下两个重要数组:

  • dfn[]:表示深度优先遍历图时节点 \(u\) 被遍历到的次序,即时间戳。
  • low[]:节点 \(u\) 在不通过父亲走过的路的情况下可以到达节点的最小时间戳。

根据割点的定义可知,如果一个节点 \(ver\) 是割点,那么必然有一个处于其 DFS 序子树内的节点 \(to\) 使得:

\[low_{to} \ge dfn_{ver} \]

这个意思指的是无论如何走,\(to\) 都无法到达 \(ver\) 以上的节点,不能回到祖先,那么 \(ver\) 即为割点。

然而当 \(ver\) 作为搜索的起始点时,由于 \(ver\) 以上没有父亲节点,自然无法判断其是否是割点,这种方法并不适用,对于这种情况,我们可以直接特判:记录从 \(ver\) 节点开始可以到达的子节点数量,如果大于 \(1\),则 \(ver\) 肯定是割点;而如果只有一个儿子的话,删掉 \(ver\) 不会发生任何影响。

考虑如何在搜索的过程不断更新 low[] 数组:

  1. 当遍历到当前点 \(ver\) 时,令 \(low_{ver} \gets dfn_{ver}\)。

  2. 遍历子节点 \(to\) 时,如果 \(to\) 已经被更新过(\(dfn_{to}\) 有值),那么边 \(ver \to to\) 为非树边,要么为前向边(我们不用处理),要么为返祖边(令 \(low_{ver} \gets dfn_{to}\)​)。

  3. 否则,由于 \(to\) 没有被遍历过,在 \(ver\) 的搜索子树当中,我们继续搜索 to 的子树,并将传递的值返回,令 \(low_{ver} \gets \min(low_{ver}, low_{to})\)。

伪代码如下(摘自 OI Wiki):

\[\begin{array}{ll} 1 & \textbf{if } v \text{ is a son of } u \\ 2 & \qquad \text{low}_u = \min(\text{low}_u, \text{low}_v) \\ 3 & \textbf{else} \\ 4 & \qquad \text{low}_u = \min(\text{low}_u, \text{dfn}_v) \\ \end{array} \]

注意

由于 low[] 数组在 DFS 序子树中具有传递性,直接在子树中传递 low[ver] = min(low[ver], low[to]) 是没有任何问题的。

而如果边 \(ver \to to\) 是一条返祖边时,采取 low[ver] = min(low[ver], low[to]) 的更新方式会使得之后的点可以回溯到 \(ver\) 的其他点更新时重复上跳,违反了 low[] 数组的初始定义,导致出错。况且 low[] 数组的核心用处是判断 \(low_{to} \ge dfn_{ver}\) ,并非求最值,它仅需要找到一个比 \(ver\)​ 更小的点即可,因此 low[ver] = min(low[ver], dfn[to]) 的正确性成立。

详见:关于有向图 Tarjan 算法模板的一些疑问

代码

P3388 【模板】割点(割顶)

给出一个 \(n\) 个点,\(m\) 条边的无向图,求图的割点。

void tarjan(int ver, int pre)
{
	dfn[ver] = low[ver] = ++ timestamp;	// 初始化时间戳
	int child = 0;	// 记录该节点为根有几个儿子
	for (int i = h[ver]; ~i; i = ne[i])
	{
		int j = e[i];
		if (!dfn[j])
		{
			child ++;
			tarjan(j, ver);
			low[ver] = min(low[ver], low[j]);
			if (ver != pre && low[j] >= dfn[ver] && !flag[ver])
				res ++, flag[ver] = true;	// 找到一个割点
		}
		else if (j != pre)
			low[ver] = min(low[ver], dfn[j]);
	}
	if (ver == pre && child >= 2 && !flag[ver])
		res ++, flag[ver] = true;	// 特判根节点
}

割边(桥)

与割点的定义类似,如下:

对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。

Tarjan

处理过程

与 Tarjan 算法求解割点的方法类似,我们同样定义两个数组 dfn[]low[] 处理,对于一条割边,以它连接的子树必然无法通过别的边到达它上面的点,即对于一条在 DFS 树上的 \(ver \to to\) 边 \(edge\):

\[low_{to} \gt dfn_{ver} \Leftto egde \in \text{Bridge} \]

需要注意的是,在标记一条边时,同时要标记它的反边。

代码

void tarjan(int ver, int from)
{
	dfn[ver] = low[ver] = ++ timestamp;
    for (int i = h[ver]; ~i; i = ne[i])
    {
		int to = e[i];
        if (to == (from ^ 1)) continue;
       	if (!dfn[to])
        {
			tarjan(to, i);
            low[ver] = min(low[ver], low[to]);
            if (low[to] > dfn[ver])
                bridge[i] = bridge[i ^ 1] = true, ++ ans;
        }
        else low[ver] = min(low[ver], dfn[to]);
        
    }
}

Reference

割点和桥 - OI Wiki (oi-wiki.org)

P3388 【模板】割点(割顶) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

图论基础 - qAlex_Weiq - 博客园 (cnblogs.com)

标签:ver,min,割点,笔记,dfn,low,节点,模板
From: https://www.cnblogs.com/ThySecret/p/18524698

相关文章

  • 【笔记/模板】线段树(改)
    线段树线段树是OI竞赛中最强大的数据结构之一,可以用来维护和、积以及最值等具有合并性质的信息。一般线段树P3372【模板】线段树1-洛谷|计算机科学教育新生态(luogu.com.cn)P3373【模板】线段树2-洛谷|计算机科学教育新生态(luogu.com.cn)以模板一为例:cla......
  • 【笔记/模板】无向图的双连通分量
    边双连通分量定义在一张联通的无向图中,对于任意两点\(u\)和\(v\)​,删去两点之间任意一条边,都无法使其不连通(即连通数不变),我们就说这两点是边双连通。对于一个无向图中的极大边双连通的子图,我们称这个子图为一个边双连通分量。根据【笔记/模板】割点和桥中可知,如果......
  • 【笔记/模板】拓扑排序
    www.luogu.com.cn拓扑排序定义与实现思路拓扑排序(TopologicalSorting)是一个有向无环图(DAG,DirectedAcyclicGraph)的所有顶点的线性序列。且该序列必须满足下面两个条件:每个顶点出现且只出现一次。若存在一条从顶点A到顶点B的路径,那么在序列中顶点A出现在顶点B......
  • 【笔记/模板】树状数组
    原理解释树状数组是一种通过前缀和和差分的思想所进行的维护数组,从而以\(O(\logn)\)的时间复杂度进行修改和查询。一共有四种修改和查询的方式,分别是:单点修改\(+\)区间询问区间修改\(+\)单点询问单点修改\(+\)区间询问(二维)区间修改\(+\)区间询问其中利......
  • 【模板】矩阵运算
    不进行没必要的解释,主要记录模板。structMatrix{intn,m,rec[N][N]; //矩阵的长,宽和二维数组Matrix(int_n,int_m){n=_n,m=_m,memset(rec,0,sizeofrec);} //初始化函数voidreset(){n=0,m=0,memset(rec,0,sizeofrec);}......
  • 【笔记/模板】最近公共祖先(LCA)
    最近公共祖先(LCA)定义最近公共祖先(LowestCommonAncestor)简称LCA。对于一个树上的两个节点的最近公共祖先,是这两个点中的公共祖先里面离根最远的一个。性质可见OIWiki。向上标记法过程在两点中取得深度较大的一个点,让它不停的向上跳,同时标记所经过的每一个点,直到根节点,接......
  • 【笔记/模板】最小生成树
    www.luogu.com.cn概念/定义一个连通图的生成树是一个极小的连通子图,它包含图中全部的\(n\)个顶点,但只有构成一棵树的\(n-1\)条边。而最小生成树就是一个带权图的生成树,并且使得原图中边的权值最小的生成树,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。......
  • 【模板】Floyd算法
    Floyd算法原理Floyd算法用来求出任意两个节点之间的最短路。优点:代码少,思维简单,适用于除了负环以外的任何图。缺点:时间复杂度为\(O(n^3)\),空间复杂度为\(O(n^2)\)。而Floyd的核心原理是用动态规划实现的,定义一个二维数组\(f_{i,j}\),遍历图上的所有点\(k\),可以得......