tk's blog
  • tk's blog Read Me
  • 算法相关
    • 数据结构
      • 【集训整理】 旋转treap模板
      • 二叉树及相关数据结构的java语言实现
      • 快乐树0x01:AVL树的java实现
      • 快乐树0x02 线段树实现(c++)
      • 链表的Java语言实现
    • 算法
      • DP的背包问题小结-java语言描述
      • 【集训整理】2-SAT问题 模板题
      • 【集训整理】Tarjan算法 模板题
      • 【集训整理】差分约束 模板题
      • 【集训整理】最近公共祖先LCA 模板题
      • 二分查找与二分答案-java实现
      • 动态规划-java语言练习一:暴力DP
      • 快速幂
      • 状态压缩DP-java描述
      • 差分
      • 乘法逆元
    • 题解
      • CFRound-GoodBye2022题解
  • java相关
    • Java与算法竞赛——注意事项摘录
    • java面向对象简要总结 一
    • java面向对象简要总结 三
    • java面向对象简要总结 二
  • 后端相关
    • Linux-Crontab命令
    • Spring Data JPA 使用方法
    • Spring集成Artemis实现JSM的异步消息传递
    • Spring使用自定义配置项
    • MIT6.824分布式系统Lab1.MapReduce笔记
    • MIT6.824分布式系统Lab2-Raft-A笔记
    • MIT6.824分布式系统Lab2-Raft-B笔记
  • 杂谈
    • 杂谈-关于2021
  • 杂项
    • c语言 scanf的返回值
    • 系统设计
  • 计科基础
    • 编译原理
      • 编译原理:词法分析笔记
    • CSAPP 第二章笔记
    • 计算机组成原理笔记
    • CSAPP Lab1. Datalab
    • CSAPP Lab2 Bomblab
  • C++每日一题
    • C++每日一题 Day 1 肥宅水
    • C++每日一题 Day 2 数字反转
    • C++每日一题 Day 3 理五的凡尔赛风气
    • C++每日一题 Day 4 我喜欢这个数
    • C++每日一题 Day 5 数字楼梯
    • C++每日一题 Day 6 插火把
    • C++每日一题 Day 7 贪吃蛇
    • C++每日一题 Day 8 蒙德最强战力
    • C++每日一题 Day 9 璃月七星选举
    • C每日一题 Day 2 肥宅水
    • C每日一题 Day 3 理五的凡尔赛风气
    • C语言每日一题 Day 1 荧妹好感队
由 GitBook 提供支持
在本页
  • 桥
  • 割点
  • 边双连通分量
  • 点双连通分量(vDCC)
  • 强连通分量
  1. 算法相关
  2. 算法

【集训整理】Tarjan算法 模板题


题面:

给你一个 n 个点,m* 条边的无向图简单图。求割点数量,割边数量,极大点双连通分量数量,极大点双连通分量包含边数的最大值。

割点:在图中移除这个点后,存在一个点对在原图中连通在新图中不连通。

割边:在图中移除这条边后,存在一个点对在原图中连通在新图中不连通。

点双连通分量:原图的一个点数大于 1 的连通子图,不存在对于这个子图的割点。

极大点双连通分量:是点双连通分量,且任意新增一个点后不是点双连通分量。

Tarjan主要基于dfs的思想,用来求解图的连通性问题。算法思想:

  1. 时间戳:记录在dfs时每个截点被访问的顺序,用dfn[x]来表示。

  2. 搜索树:从某个节点出发进行dfs,访问到的边和节点构成的树。

  3. 追溯值:用low[x]表示,表示满足下列条件的节点中dfn的最小值:

    • x为根的搜索树中的所有节点

    • 通过一条不在搜索树上的边,能到达搜索树的节点

这样追溯值就表示x点属于包含low[x]节点的环(如果有环的话)。

追溯值的计算方法(dfs回溯的时候算):

先让low[x]=dfn[x]low[x] = dfn[x]low[x]=dfn[x],然后对x的每条边能到达的点y:

  • 若y在x搜索树上(y>x),则low[x]=min(low[x],low[y])low[x] = min(low[x],low[y])low[x]=min(low[x],low[y])

  • 若y不在x的搜索树上(y<x),则low[x]=min(low[x],dfn[y])low[x] = min(low[x],dfn[y])low[x]=min(low[x],dfn[y])

桥

边(x,y)为桥当且仅当dfn[x]<low[y]dfn[x]<low[y]dfn[x]<low[y]

如果low[y]<=dfn[x]low[y]<=dfn[x]low[y]<=dfn[x],说明有另一条路可以连回x以上,说明该边不是桥。

割点

点x是割点当且仅当dfn[x]<=low[y]dfn[x]<=low[y]dfn[x]<=low[y]

就算回路连回x点,删掉x点还是能把图拆断

参考代码:

void tarjan(int x){
	dfn[x]=low[x]=++num;
	int flag=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=flag||flag>1){
					cur[x]=1;
				}
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

边双连通分量

定义:没有割边的分量

去掉桥后dfs即可

点双连通分量(vDCC)

在tarjan过程中维护一个栈:

当第一次访问一个节点时,将其入栈;当dfn[x]<=low[y]dfn[x]<=low[y]dfn[x]<=low[y]成立时(找到割点),一直弹栈直至y被弹出,x->y构成一个vDCC

参考代码:

void tarjan_dcc(int x){
	dfn[x]=low[x]=++num;
	stac[++top]=x;
	if(x==root&&head[x]==0){
		//孤立点
		dcc[++cnt].push_back(x);
		return ;
	}
	int flag=0;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan_dcc(y);
			low[x]=minn(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1)cur[x]=1;
				cnt++;
				
				int z;
				do{
					z=stac[top--];
					dcc[cnt].push_back(z);
				}while(z!=y);

				dcc[cnt].push_back(x);
			}
		}
		else low[x]=minn(low[x],dfn[y]);
	}
}

强连通分量

注意点双是无向图的概念,强连通分量是有向图的概念。

与求点双的方法类似,但是强连通要求dfn[x]==low[y]dfn[x]==low[y]dfn[x]==low[y]时才能开始退栈。

参考

[tarjan算法(新) | Liyue (theshineyue.github.io)](https://theshineyue.github.io/2021/10/30/Tarjan 算法总结/)

上一页【集训整理】2-SAT问题 模板题下一页【集训整理】差分约束 模板题

最后更新于2年前

60 分钟搞定图论中的 Tarjan 算法(一) - 知乎 (zhihu.com)