浅谈 Tarjan 算法

这篇具有很好参考价值的文章主要介绍了浅谈 Tarjan 算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在了解 Tarjan 算法之前,我们先来了解 dfs 搜索树。

1 dfs 生成树

定义: dfs 遍历整张图,按照 dfs 序构成一棵树。

1.1 有向图的 dfs 生成树

tarjan算法,学习笔记,算法

有向图的 dfs 生成树包括四种边:

  • 树边(tree edge):图中黑色边表示。表示搜索访问到未访问过的结点。
  • 回边(back edge):图中橙色边表示。表示该边指向先前访问过的祖先。
  • 叉边(cross edge):图中蓝色边表示。表示该边指向先前访问过的非祖先结点。
  • 前向边(forward edge):图中红色边表示。表示该边指向先前访问过的孩子结点。

1.2 无向图的 dfs 生成树

tarjan算法,学习笔记,算法
无向图的 dfs 生成树仅包含两种边:树边和回边。

证明没有叉边和前向边:

  • 如果存在叉边 u → v u \to v uv,其中 u u u 为当前搜索访问到的结点, v v v 为之前访问过的非祖先结点,那么在访问 v v v 时,就应该访问了 u u u,与 u u u 为当前搜索访问到的结点矛盾。

  • 如果存在前向边 u → v u \to v uv ,那么在首次访问 v v v 时,该边就会作为一条回边指向 u u u ,不会作为 u → v u \to v uv 一条前向边。


2 Tarjan 算法

2.1 桥

题目

2.1.1 桥的定义

无向图中,若删去一条边会使得这个图的极大连通分量数增加,则该边被称为桥。

也可以理解为无向图的一个连通块中,若删除一条边会使得至少两点之间无法相互到达,该边被称为桥。

2.1.2 实现

样例:
tarjan算法,学习笔记,算法
样例中, 1 → 2 1 \to 2 12 5 → 6 5 \to 6 56 就是该图的桥。

  • 容易发现,只有 树边 才可能作为桥,而 dfs 生成树中红色的回边 4 → 2 4 \to 2 42 标记了 2 → 3 → 5 → 4 2 \to 3 \to 5 \to 4 2354 沿途上的树边都不可能作为桥。因此我们得出结论:一条边是桥,当且仅当它是 不被回边标记的树边

在 Tarjan 算法中,我们对每个点 u u u 按 dfs 序打上时间戳 d f n u dfn_u dfnu,同时记录 l o w u low_u lowu 表示 u u u 不经过其父亲能到达的最小时间戳,即按照 dfs 生成树中有向边能到达的最小时间戳。

那么一条树边 u → v u \to v uv 不被回边标记的充要条件即为: l o w v > d f n u low_v > dfn_u lowv>dfnu。如例中, 1 → 2 1 \to 2 12low[2]=2,dfn[1]=1,可以得到 1 → 2 1 \to 2 12 就是一座桥。

void Tarjan(int u, int fa)
{
	dfn[u] = low[u] = ++ idx;
	for(auto v : G[u])
	{
		if(v == fa) continue;
		
		if(!dfn[v]) // tree edge 
		{
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u]) // is bridge
				bridge[u][v] = 1;
		}
		
		else // back edge 
			low[u] = min(low[u], dfn[v]);
	}
}

2.2 割点

题目

2.2.1 割点的定义

无向图中,若删去一个点会使得这个图的极大连通分量数增加,这个点被称为割点。

也可以理解为无向图的一个连通块中,若删除一个点会使得至少两点之间无法相互到达,该点被称为割点。

2.2.2 实现

tarjan算法,学习笔记,算法
首先,由于图不连通,我们大体的决策是将图分成若干连通块,在每个连通块对应的 dfs 生成树上进行搜索。

  • 对于结点 5 5 5,删去 5 5 5 显然不会对儿子结点 3 , 4 3,4 3,4 造成影响,因为它们有回边可以连到结点 5 5 5 的祖先,而对于儿子结点 6 6 6 会有影响,其没有回边可以连到可以连到结点 5 5 5 的祖先。

    我们推广到一般情况:对于结点 u u u ,若存在儿子结点的 l o w v ≥ d f n u low_v \ge dfn_u lowvdfnu ,即 v v v 没有回边可以连到结点 u u u 的祖先,那么 u u u 一定是个割点。

  • 然而 1 1 1 号虽然满足上述条件,然而 1 1 1 并不是割点。

    因此我们还需判断一种情况,即 u u u 作为了 dfs 搜索树的根节点,不论如何其任何儿子 v v v l o w v low_v lowv 都不可能小于 d f n u dfn_u dfnu ,因此需要分开讨论:当 u u u 作为根节点时,若 u u u 有两个及以上的儿子时, u u u 为割点。

int dfn[N], low[N], idx, cnt;
bool cut[N];
void Tarjan(int u, int fa)
{
	dfn[u] = low[u] = ++ idx;
	
	int son = 0;
	
	for(auto v : G[u])
	{	
		if(v == fa) continue;
		
		if(!dfn[v])
		{	
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			
			son ++ ;
			if(fa != 0 and low[v] >= dfn[u] and !cut[u]) cnt ++ , cut[u] = 1;
		}
		
		else low[u] = min(low[u], dfn[v]);
	}
	
	if(fa == 0 and son >= 2 and !cut[u]) cnt ++ , cut[u] = 1;
	
}

代码

2.3 强连通分量

题目

2.3.1 强连通分量的定义

注意,强连通分量(SCC,Strongly Connected Components)是在单向图中的。

强联通子图,定义为:在 单向图 中,该子图上的任意两点之间能互相到达。

强联通分量,定义为:极大连通子图

2.3.2 实现

以下图为例:

tarjan算法,学习笔记,算法

该例中强连通分量为 { 1 , 2 , 3 , 4 , 5 , 6 , 7 } \lbrace 1,2,3,4,5,6,7 \rbrace {1,2,3,4,5,6,7}

前向边没用。

  • u u u 是当前 scc 第一个被访问的结点,那么该 scc 的结点一定在 dfs 生成树中以 u u u 为根的子树内。

    证明:若存在该 scc 中的点 v v v 不在 u u u 子树内,则 u u u v v v 的路径中一定存在叉边或回边,根据叉边、回边的定义,则 v v v u u u 之前已经被访问过,与 u u u 是当前 scc 第一个被访问的结点矛盾。

  • 如果我们把单个节点也算作是强连通分量,那么所有 scc 的根应 u u u 当都满足 l o w u = d f n u low_u=dfn_u lowu=dfnu

具体实现

考虑使用一个栈 s s s 存储遍历到的结点,每当访问到一个 l o w u = d f n u low_u=dfn_u lowu=dfnu 的结点,就将栈内元素从栈顶 弹出直至 u u u ,这些结点即为以 u u u 为根的强连通分量。

在遍历 u u u 的子树过程中,确实有可能会遍历到其他强连通分量的点,根据树的结构,一定会先遍历到其他 scc 的根 v v v,而在遍历 v v v 的过程中,发现了 l o w v = d f n v low_v=dfn_v lowv=dfnv ,便会将栈内的元素弹出直到 v v v,因此在遍历完 u u u 的子树后仍然留在栈中的元素一定是以 u u u 为根的 scc 中的元素。

而在搜索过程中,我们会遍历到以下三种结点:

  • 未访问的结点:该边为树边,将 v v v 入栈,对 v v v 进行 dfs,更新 l o w low low

  • 访问过并且不在栈中:该边为叉边或前向边,说明已经是其他 scc 中的结点,对当前 scc 不会产生任何影响,忽略。

  • 访问过并且在栈中:该边为叉边、前向边或回边,更新 l o w low low 值。

int low[N], dfn[N], idx;
bool ins[N];
int tot, belong[N];

stack <int> s;

void Tarjan(int u)
{
	low[u] = dfn[u] = ++ idx;
	
	s.push(u); ins[u] = 1;
	
	for(auto v : G[u])
	{
		if(!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		if(dfn[v] and ins[v]) 
			low[u] = min(low[u], dfn[v]);
	}
	
	if(low[u] == dfn[u]) // 当前 scc 的根
	{
		++ tot;
		while(s.top() != u) // 出栈,标记结点所属 scc
		{
			int x = s.top(); s.pop();
			belong[x] = tot, ins[x] = 0;
		}
		s.pop(); belong[u] = tot, ins[u] = 0;
	}
	
}

代码

2.3.3 强连通分量缩点

在无向图的一些问题中,若将所有 scc 合并为一个点,那么这张无向图就会变成一张有向无环图(DAG,Directed Acyclic Graph)。

因此我们只需保留连接两个不同 scc 的边来构成缩点后的新图。

	for(int i=1; i<=n; i++)
	{
		if(!dfn[i])
			idx = 0, Tarjan(i);
	}
	
	for(int u=1; u<=n; u++) // 缩点后的图 e
	{
		for(auto v : G[u])
		{
			int x = belong[u], y = belong[v];
			if(x != y)
				e[x].push_back(y);
		}
	}

[模板] 缩点

题目

由于题目存在环且能多次经过同一点,直接在图上进行搜索显然不可行。

由于点权均为非负数,在经过一个环时,显然应当经过还上的所有点,此时我们考虑缩点,将图变成一张 DAG ,然后用记忆化搜索或者拓扑排序求解最长路径即可。

2.4 双联通分量

无向图中,双联通分量包含点 点双联通分量边双联通分量

2.4.1 双联通分量的定义
  • 点双联通:对于点 u u u v v v ,删去图上任意一个点, u u u v v v 始终连通,则称 u u u v v v 点双联通。

    容易发现,若一个子图点双连通,那么这个子图上一定不存在割点。

  • 边双连通:对于点 u u u v v v ,仅删去图上任意一条边, u u u v v v 始终连通,则称 u u u v v v 双联通。

    容易发现,若一个子图边双连通,那么这个子图上一定不存在桥。

  • 点双连通分量:极大点双连通子图。

  • 边双连通分量:极大边双连通子图。

2.4.2 边双的实现

题目

在找出原图上的桥后,将其在原图中去掉,剩下的连通块即为边双连通分量。

int cnt; 
bool vis[N];
vector <int> dcc[N];
void dfs(int u)
{
	vis[u] = 1;
	dcc[cnt].push_back(u);
	for(int i=head[u]; i; i=e[i].nxt)
	{
		if(vis[e[i].v] or bridge[i]) continue;
		dfs(e[i].v);
	}
}

代码

2.4.3 边双缩点

我们将每个边双看作一个新节点,原图上的桥看作连接边双之间的边,这样新图会构成一棵树。

for(int i=2; i<=tot1; i++)
	{
		int u = e1[i].v, v = e1[i ^ 1].v;
		int x = belong[u], y = belong[v];
		if(x != y) add_edge2(x, y);
	}
[NOIP2022] 建造军营

题目

在边双中的任意两点之间都不需要保护道路,考虑边双缩点。由于原图为连通图,边双缩点后变为一棵树,进行树 dp 统计答案。

2.4.4 点双的实现

详见圆方树章节。文章来源地址https://www.toymoban.com/news/detail-752915.html

到了这里,关于浅谈 Tarjan 算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Tarjan 算法(超详细!!)

    推荐在 cnblogs 上阅读 说来惭愧,这个模板仅是绿的算法至今我才学会。 我还记得去年 CSP2023 坐大巴路上拿着书背 Tarjan 的模板。虽然那年没有考连通分量类似的题目。 现在做题遇到了 Tarjan,那么,重学,开写! 另,要想学好此算法的第一件事——膜拜 Tarjan 爷爷。 其实广义

    2024年01月25日
    浏览(43)
  • 【图论】无向图连通性(tarjan算法)

    1. 连通 : 在图论中,连通性是指一个无向图中的任意两个顶点之间存在路径。如果对于图中的任意两个顶点 u 和 v,存在一条路径从 u 到 v,那么图被称为连通图。如果图不是连通的,那么它可以被分为多个 连通分量 ,每个连通分量都是一个连通子图。 2.割点: 割点(Cut V

    2024年02月13日
    浏览(43)
  • 20 求图的割点和割边—Tarjan算法

    问题描述 去掉2号城市,这样剩下的城市之间就不能两两相互到达。例如4号城市不能到5号城市,6号城市也不能到达1号城市等等。 下面将问题抽象化。在一个无向连通图中,如果删除某个顶点后,图不再连通(即任意两点之间不能相互到达),我们称这样的顶点为割点(或者

    2024年02月15日
    浏览(34)
  • 每天一道leetcode:1192. 查找集群内的关键连接(图论&困难&tarjan算法)

    力扣数据中心有 n 台服务器,分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群,连接是无向的。用 connections 表示集群网络, connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络

    2024年02月12日
    浏览(49)
  • 【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

    目录: 今天知识点 加边使得无向图图变成双连通图 找出度为0的强连通分量 加边使得有向图变成强连通图 将有向图转成DAG图进行dp          POJ3352:道路建设         思路: POJ2553:图的底部 思路: POJ1236校园网络 思路: 缩点:  思路:          由于道路要维修

    2024年02月05日
    浏览(43)
  • AcWing1171. 距离(lca&&tarjan)

    输入样例1: 输出样例1: 输入样例2: 输出样例2:

    2024年02月14日
    浏览(35)
  • LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,

    2023年04月20日
    浏览(42)
  • 第三章 图论 No.8最近公共祖先lca, tarjan与次小生成树

    O ( m l o g n ) O(mlogn) O ( m l o g n ) ,n为节点数量,m为询问次数,lca是一种在线处理询问的算法 自己也是自己的祖先 倍增: f a ( i , j ) fa(i, j) f a ( i , j ) 表示从i开始,向上走 2 j 2^j 2 j 步走到的点 j = 0,走到父节点 j 0,分两步走,先走到 2 j − 1 2^{j-1} 2 j − 1 步再走 2 j − 1 2^{

    2024年02月13日
    浏览(44)
  • Codeforces Round 916 (Div. 3)(E:贪心 F贪心dfs G tarjan+topsort +线段树优化建图)

    A:直接暴力统计每个字符的次数是否达标即可 B:直接先输出所需要的k,然后降序输出剩下的即可 C: 直接枚举最后操作到哪个位置就行了,然后贪心一直操作1到i的位置的b最大值即可 D: 先固定第一次是A 第二次是B 第三次是C 枚举B为中介点i,然后求1到i-1的A的最大值,和

    2024年01月17日
    浏览(41)
  • Lua学习笔记:浅谈table的实现

    前言 本篇在讲什么 Lua中的table的实现 本篇适合什么 适合 初学Lua 的小白 本篇需要什么 对 Lua 语法有简单认知 依赖 Sublime Text 编辑器 本篇的特色 具有全流程的 图文教学 重实践,轻理论,快速上手 提供全流程的 源码 内容 ★提高阅读体验★ 👉 ♣ 三级标题 👈 👉 ♦ 四级标

    2024年02月12日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包