首页 > 编程语言 >tarjan算法

tarjan算法

时间:2024-11-02 17:11:38浏览次数:1  
标签: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.Prim算法(卡码网53)#最小生成树prim算法#贪心地选择距离已有集合最小的边加入defprim(graph)->int:result=0visited=[Falsefor_inrange(len(graph))]#未选点距离已选集合的最短距离minDist=[10001for_inrange(len(graph))]......
  • 【算法】【优选算法】双指针(上)
    目录一、双指针简介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. 觅食行为:小龙虾会在其感知范围内搜索食物资源。它们朝着食物浓度......
  • 遗传算法+强化学习—TPG—Emergent Tangled Graph Representations for Atari Game Pl
    最近在看进化算法在强化学习(RL)领域的一些应用,有些论文中将使用进化算法解决强化学习问题的算法归为非强化学习算法,然而又有些论文把使用进化算法解决强化学习问题的算法归为强化学习算法,不过更多的论文是不讨论进化算法解决强化学习问题的,由此就出现了大多数论文只讨论使用MDP框......
  • 基于深度学习的机器人智能控制算法 笔记
    正解/逆解求正解/逆解有现成的库,参考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、堆的性质堆的存储......