首页 > 编程语言 >tarjan算法

tarjan算法

时间:2024-11-02 17:11:38浏览次数:3  
标签:tarjan ++ int stpos 算法 dfn low

强连通分量

细节

对于多点跑tarjan来说,可能会有先访问\(u\to v\)中的\(v\),这导致\(dfn[v]<dfn[x]\),后面\(x\)跑tarjan时会误把\(v\)当成祖先,要加判断

割点 & 割边

删去后使图不连通的点/边

找割边和强连通分量求法大差不差,这里不再赘述

找割点不同于前两者,首先割点不是low[x]==dfn[x]的点,而是存在树边连接的儿子low[v]>=dfn[x]的点,其次树根要特判

无向图连通分量

定义

边双:对于一个边双连通图,图上任意两点都有至少两条边不相交的道路(包括孤立点)

点双:对于一个点双连通图,图上任意两点都有至少两条点不相交的道路(包括孤立点)

其实这两种唯一的差别在于点双包含一种特殊情况——“杠铃形”子图,即两点有且仅有一条边相连,且该边为割边

由此引出另一个弱化的定义:

边双:不存在割边的连通图(包括孤立点)

点双:不存在割点的连通图(包括孤立点和“杠铃形”)

发现后面两个定义更易实现

细节

两者的实现有差别

边双更好理解,因为把所有割边去掉就得到所有边双,于是在tarjan找割边时顺便退出即可

点双不太一样,利用了点双的一些性质:

1、所有边在且仅在一个点双上;

2、两个点双间一定以割点分隔;

考虑在割点处进行统计,在判low[v]>=dfn[x]后即可弹栈获取v所在点双,注意不要把割点给弹了

还有一件事:点双弹栈是以v为分界点的,不是x,栈内x,v之间可能有别的儿子

代码

边双:

void tarjan(int x,int pre) {
	dfn[x]=low[x]=++index;
	st[++stpos]=x;
	erg(x,i) {
		int v=e[i].to;
		if(i==(pre^1)) continue;
		if(!dfn[v]) {
			tarjan(v,i);
			low[x]=min(low[x],low[v]);
		}
		low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x]) {
		stot++;
		while(st[stpos+1]!=x) scc[stot].push_back(st[stpos--]);
	}
}

点双:

void tarjan(int x,int pre) {
	dfn[x]=low[x]=++index;
	st[++stpos]=x;
	int son=0;
	erg(x,i) {
		int v=e[i].to;
		if(i==(pre^1)) continue;
		if(!dfn[v]) {
			tarjan(v,i);
			low[x]=min(low[x],low[v]);
			++son;
			if(low[v]>=dfn[x]) {
				++stot;
				while(st[stpos+1]!=v) 	//注意边界
					scc[stot].push_back(st[stpos--]);
				scc[stot].push_back(x);
			}
		}
		else low[x]=min(low[x],dfn[v]);
	}
	if(rt==x&&!son) {	//特判孤立点
		scc[++stot].push_back(st[stpos]);
	}
}

标签:tarjan,++,int,stpos,算法,dfn,low
From: https://www.cnblogs.com/zhone-lb/p/18522205

相关文章

  • 【排序算法】堆排序
    ......
  • 阿里国际2025届校园招聘 0826算法岗笔试
    目录1.第一题2.第二题3.第三题⏰时间:2024/08/26......
  • 常用算法模板
    快速排序defquick_sort(arr):iflen(arr)<=1:#基本情况:如果数组为空或只有一个元素,则返回returnarrelse:pivot=arr[0]#选择基准值(可以选择第一个元素)less_than_pivot=[xforxinarr[1:]ifx<=pivot]#小于等于基准值......
  • 【算法】【优选算法】双指针(上)
    目录一、双指针简介1.1对撞指针(左右指针)1.2快慢指针二、283.移动零三、1089.复写零3.1双指针解题3.2暴力解法四、202.快乐数4.1快慢指针4.2暴力解法五、11.盛最多⽔的容器5.1左右指针5.2暴力解法一、双指针简介常⻅的双指针有两种形式,⼀种是对撞指针,⼀......
  • 基于SpringBoot的电视剧推荐系统设计与实现(源码+定制+开发)电视剧推荐系统、个性化影
    博主介绍:  ✌我是阿龙,一名专注于Java技术领域的程序员,全网拥有10W+粉丝。作为CSDN特邀作者、博客专家、新星计划导师,我在计算机毕业设计开发方面积累了丰富的经验。同时,我也是掘金、华为云、阿里云、InfoQ等平台的优质作者。通过长期分享和实战指导,我致力于帮助更多学生......
  • 小龙虾优化算法:原理、与遗传算法区别及应用案例
     一、小龙虾优化算法原理 (一)自然界中的小龙虾行为模拟 小龙虾优化算法(CrayfishOptimizationAlgorithm,COA)是受小龙虾在自然环境中的生存行为启发而提出的。在自然界中,小龙虾有以下几种主要行为: 1. 觅食行为:小龙虾会在其感知范围内搜索食物资源。它们朝着食物浓度......
  • 基于深度学习的机器人智能控制算法 笔记
    正解/逆解求正解/逆解有现成的库,参考https://github.com/petercorke/robotics-toolbox-python,代码如下:importroboticstoolboxasrtbimportnumpyasnpnp.set_printoptions(precision=6,suppress=True)robot=rtb.models.Panda()qr=np.array([0,-0.3,0,-2.2......
  • 【排序算法】堆排序
    堆排序堆的认识1、什么是堆在堆排序中,堆是一种特殊的二叉树,它满足以下两个条件一颗完全二叉树,按照整体从上到下,同一层从左到右的顺序排列,不包括平衡树。当父节点的值≥左右孩子的值,根节点的值为最大值时称为大根堆或大顶堆,反之称为小根堆(小顶堆)。2、堆的性质堆的存储......