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挺有意思的一道题

Tarjan算法

相关推荐

从 Excel 营业流水到可验证测试订单：测试数据导入工具工程复盘

Node.js 中使用 Mongoose 的完整步骤与配置方法：TaoToken 统一 Key 接入实践

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

更多资讯

你管这破玩意叫 MCP？用 TaoToken 统一 Key 打通 Cline 配置

EtherCAT实时以太网：从站开发与多轴伺服同步实战

邮件安全四层防线：从账号加固到SPF/DKIM/DMARC部署

使用 AWS SDK for Rust 调用 AWS IoT Greengrass V2：ListCoreDevices 示例实战

常见网络攻击原理与防御：从SQL注入到DDoS的实战指南

Sass 安装与命令行编译：用 TaoToken 统一 Key 打通 SCSS 工作流

今日更新

开源模型端侧落地实战：量化、推理加速与Agent上下文管理

AI Evals实战指南：从零搭建LLM应用评估体系与CI/CD集成

Java采购管理系统实战：从数据库设计到事务一致性

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？