Tarjan算法

发布时间:2026/11/21 14:19:21

Tarjan算法 我们先来了解一下Tarjan算法的作用Tarjan算法解决的是在有向图里找连通分量的问题连通分量听起来很高大上对吧但是实际上他就是一堆点它们两两之间可以互相到达像这样1 - 2 - 3 - 4 ^ | | | |--------------| 这里1,2,3,4就是一个连通分量因为从任意一个点出发都能绕一圈到达另一个点没错Tarjan实现的问题就是这么简单可是我们能用瞪眼法看出来但是机器做不到我们该怎么用一个高效的算法解决这个问题呢Tarjan算法的核心思想Tarjan用一次DFS就可以找连通分量我们DFS的时候会有两个很重要的编号我们在这里提前埋个伏笔dfn[u],low[u]它们非常的重要dfn[u]表示点u是第几个被访问到的如果通俗一点就是dfs序还是举一个例子吧假如说这棵树是这样的那么它的dfs序就是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4 dfn[5]5我们理解了dfn[]之后需要理解low[]它十分重要。low[u]表示从u出发沿着dfs序往下走最多再通过一条返祖边能够到达的最早的dfn概念返祖边就是从图里抠出来了一颗树这棵树上有一个节点可以直接通过一条边连接到它的祖先哎呀其实说人话就是low[u]记录u或u的后代、最早能绕回哪一个祖先我们可以从这一张图片来理解low[u]看到这张图大众第一次看可能会觉得low[4]1实则不是的low[4]2因为是“最多通过一条返祖边”那么说到这里我们就可以开始学习新算法了我就问一个问题假如说有一个点u使得dfn[u]low[u]我们能不能确定它是某一个连通分量这里思路跳了实在想不出就继续看吧我们还是回到这个例子1 - 2 - 3 - 4 ^ | | | |--------------|从1开始DFS1访问2 2访问3 3访问4 4又能访问1于是dfn[1]1 dfn[2]2 dfn[3]3 dfn[4]4;但是4能回到1所以low[4]1然后3的儿子4能回到12的儿子3能通过4回到1所以low[2]1 low[3]1low[1]自己肯定是等于1的这个没啥好说的最后我们发现dfn[1]low[1]这真是一个惊天的发现这说明了1是这一整个连通分量里最早被访问到的点也就是一整个连通分量的“根”呃你就这么理解吧于是Tarjan就把栈从栈顶一直弹到1的点拿出来他们就是一个连通分量1,2,3,4懵逼的同学们太懵逼了不是这从哪里又冒出来一个栈啊其实是这样的DFS的过程中有点已经访问过了但是我们不知道它们属于哪一个连通分量所以Tarjan用一个栈保存这些“还没分组“的点访问一个点的时候把它压栈st[top]u; ins[u]true;其中有一个ins[u]表示u现在是否还在栈里当确定某个点u是连通分量的”根“也就是dfn[u]low[u]就开始弹栈while(true){ int xst[top--]; ins[x]false; id[x]scc; if(xu) break; }从栈顶一直弹到u为止这些点就是一个连通分量Tarjan的DFS过程所以Tarjan的核心代码就是这样的voidTarjan(intu){dfn[u]low[u]tm;st[top]u;ins[u]true;for(intv:g[u]){if(!dfn[v]){Tarjan(v);low[u]min(low[u],low[v]);}elseif(ins[v]){low[u]min(low[u],dfn[v]);}}if(dfn[u]low[u]){scc;while(true){intxst[top--];ins[x]false;id[x]scc;if(xu)break;}}}典例演习我这里有两道例题板子题你们可以拿来练练手反正我后面会出博客讲解https://www.luogu.com.cn/problem/P3387纯模板https://www.luogu.com.cn/problem/P2746挺有意思的一道题
延伸阅读

更多相关文章

2026/11/21 14:19:32

服装智能制造大会上的AI质检案例分享

1. AI服装制造场景 在服装智能制造大会上,AI质检成为最受关注的议题之一。传统人工质检依赖老师傅的经验与肉眼判断,效率低、漏检率高、招工难,已成为制约服装工厂产能与品质的瓶颈。随着计算机视觉与深度学习技术的成熟,AI质检正…

2026/11/22 2:21:28

深圳特种工考试官方报名入口怎么找?实操考试心里没底怕挂科

深圳特种工考试官方报名入口怎么找?实操考试心里没底怕挂科 你是不是也这样,听说要考深圳特种工证,心里直打鼓?实操考试心里没底怕挂科,怕考不过浪费时间和钱,更怕以后找工作被卡住。别急,今天我就从一个干了10年特种作业行业的人角度,给你讲讲【深…

2026/11/22 2:21:28

朱巷镇电工证培训保姆级教程:如何避开中介陷阱,顺利拿证上岗

朱巷镇电工证培训保姆级教程:如何避开中介陷阱,顺利拿证上岗 你是不是在朱巷镇听说了电工证培训,但不知道该找谁报名,怕被中介坑?别急,这篇保姆级教程帮你从头理清流程,避开那些“交钱不办事”的培训机构,真正拿到能用、能升职的电工证。…

2026/11/22 2:16:28

武汉电工证有几个考点千万别踩坑怎么应对过期换证流程

武汉电工证有几个考点千万别踩坑怎么应对过期换证流程 证书过期了不知道怎么复审延期?你不是一个人。我刚接手一个新乡的电工学员案例,他手头的低压电工证已经过了有效期,却因为不懂流程,差点耽误了项目。这种事太常见了, 千万别踩坑…

2026/11/22 0:09:40

高压电工证还能年审吗良心建议来了,学历不高也能考!

高压电工证还能年审吗良心建议来了,学历不高也能考! 你是不是也担心,自己学历不高,根本报不上高压电工证?其实不然,现在政策已经非常明确, 高压电工证还能年审 ,而且只要符合条件, 学历不是门槛 , 良心建议…

2026/11/22 0:09:40

吴江的电工证免费培训怎么报名?官方报名入口全解析

吴江的电工证免费培训怎么报名?官方报名入口全解析 你急需特种作业证才能上岗找工作,但不知道从哪里下手?别急,现在就给你讲明白【吴江的电工证免费培训】到底怎么操作,以及怎么通过 官方报名入口…

2026/11/22 0:09:40

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱 不知道去哪报名怕被中介坑?这几乎是每个需要办理或复审电工证的人的真实经历。尤其在肃州区,信息不透明、流程复杂、中介收费高又不靠谱,让很多电工从业者感到头疼。作为一个在应急管理和特种作…

2026/11/22 0:09:40

高压电工证还能年审吗良心建议来了,学历不高也能考!

高压电工证还能年审吗良心建议来了,学历不高也能考! 你是不是也担心,自己学历不高,根本报不上高压电工证?其实不然,现在政策已经非常明确, 高压电工证还能年审 ,而且只要符合条件, 学历不是门槛 , 良心建议…

2026/11/22 0:09:40

吴江的电工证免费培训怎么报名?官方报名入口全解析

吴江的电工证免费培训怎么报名?官方报名入口全解析 你急需特种作业证才能上岗找工作,但不知道从哪里下手?别急,现在就给你讲明白【吴江的电工证免费培训】到底怎么操作,以及怎么通过 官方报名入口…

2026/11/22 0:09:40

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱 不知道去哪报名怕被中介坑?这几乎是每个需要办理或复审电工证的人的真实经历。尤其在肃州区,信息不透明、流程复杂、中介收费高又不靠谱,让很多电工从业者感到头疼。作为一个在应急管理和特种作…

2026/11/21 7:57:43

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/21 0:24:21

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑