当前位置：首页 > news >正文

图论---有向图的强连通分量（Tarjan求SCC）

news 来源：原创 2025/5/10 6:46:23

强连通分量作用：有向图——>（缩点）有向无环图（DAG）

缩点：将所有连通的分量缩成一个点。

有向无环图作用/好处：求最短路/最长路可以递推，按照拓扑图从前往后递推.

x 是否在某个强连通分量中？

情况1：存在后向边指向祖先节点。

情况2：先走到横叉边，横叉边再走到祖先。

时间戳：搜索时按照DFS顺序给每个点一个编号，

对每个点定义两个时间戳：

1、dfn[u] 表示遍历到 u 的时间戳

2、low[u] 从 u 开始走，所能遍历到的最小的时间戳是什么

u 是其所在强连通分量的最高点等价于 dfn[u] == low[u]

以下是Tarjan模板

//O(n+m)时间复杂度
//求强连通分量的过程
void tarjan(int u){//刚遍历到的时候dfn[u]=low[u]=++timestamp;//时间戳stk[++top]=u,in_stk[u]=true;//栈中里面存的所有点都是//当前还没有遍历完的强连通分量的所有点//在强连通分量中，并且这个强连通分量还没有遍历完//遍历所有 u 能到的点for(int i=h[u];~i;i=ne[i]){int j=e[i];//u 还没被遍历过if(!dfn[j]){//遍历一下这个点tarjan(j);low[u]=min(low[u],low[j]);}else if(in_stk[j]){low[u]=min(low[u],dfn[j]);}}//else 里面的 j 要么是祖先要么是横叉点if(dfn[u]==low[u]){int y;++scc_cnt;do{y=stk[top--];in_stk[y]=false;id[y]=scc_cnt;}while(y!=u);}
}缩点
用邻接表存
遍历所有点，遍历 i 的所有邻点
if(i 和 j 不在同一个SCC中){加一条新边 id[i] -> id[j] 存的是i所在的连通分量的编号
}
建成的图是 有向无环图
DAG可以用拓扑排序来做
连通分量编号递减的顺序一定是拓扑序

图论---有向图的强连通分量（Tarjan求SCC）

强连通分量作用：有向图——>（缩点）有向无环图（DAG） 缩点：将所有连通的分量缩成一个点。有向无环图作用/好处：求最短路/最长路可以递推，按照拓扑图从前往后递推. x 是否在某个…...

编程日记 2025/5/10 6:46:23

2025年- H17-Lc125-73.矩阵置零（矩阵）---java版

1.题目描述 2.思路 （1）计算矩阵的行数 （2）计算矩阵的列数 （3）设计一个行列的bool数组 （4）遍历矩阵（二维数组），如果遇到元素0，则把…...

编程日记 2025/5/10 5:46:27

【信息系统项目管理师-论文真题】2023下半年论文详解（包括解题思路和写作要点）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录试题（第一批）：论信息系统项目的干系人管理1、写作要点2、解题思路项目干系人管理的过程和执行要点项目中所有干系人如何进行分类管理？试题（第二批）：论信息系统项目的工作绩效域1、写作要点2、解题思路绩…...

编程日记 2025/5/10 6:45:13

分享5款开源、美观的 WinForm UI 控件库

前言今天大姚给大家分享5款开源、美观的 WinForm UI 控件库，助力让我们的 WinForm 应用更好看。 WinForm WinForm是一个传统的桌面应用程序框架，它基于 Windows 操作系统的原生控件和窗体。通过简单易用的 API，开发者可以快速构建基于窗体…...

编程日记 2025/5/7 17:10:24

微软推出数款Phi 4“开放式”人工智能模型

微软周三推出了几款新的“开放式”人工智能模型，其中功能最强大的模型至少在一个基准测试上可与 OpenAI 的 o3-mini 相媲美。所有新的授权模型——Phi 4 mini reasoning、Phi 4 reasoning 和 Phi 4 reasoning plus——都是“推理”模型，这意味着它们能够…...

编程日记 2025/5/10 6:11:10

Python实例题：Python实现Python解释器

目录 Python实例题题目实现思路代码实现代码解释词法分析器（Lexer）： 词法单元类（Token）： 抽象语法树节点类（AST）： 语法分析器（Parser&#xff…...

编程日记 2025/5/7 13:43:50

【IP101】图像滤波技术详解：从均值滤波到高斯滤波的完整指南

🌟 图像滤波魔法指南 🎨 在图像处理的世界里，滤波就像是给图片"美颜"的魔法工具。让我们一起来探索这些神奇的滤波术吧！ 📑 目录 1. 均值滤波：图像的"磨皮"大法2. 中值滤波&#xff1…...

编程日记 2025/5/2 10:41:34

信息系统项目管理师-软考高级（软考高项）2025最新（六）

个人笔记整理---仅供参考第六章项目管理概论 6.1PMBOK的发展 6.2项目基本要素组织过程资产指的是项目上的，国产数据库的使用----安保和安全指的是环境因素 6.3项目经理的角色 6.4价值驱动的项目管理知识体系...

编程日记 2025/5/9 14:11:04

算法-堆、排序算法、矩阵乘法

满二叉树、完全二叉树二叉树遵循下面的规律，当前节点i（但是其实就是逐级填充）: 左节点为 ix2右节点为 i*21父节点为 [i/2] 向下取整使用数组表示二叉树： （二叉树的深度自上而下，高度自下…...

编程日记 2025/5/2 10:38:26

Java 进阶--集合：告别数组的“僵硬”，拥抱灵活的数据容器

作者：IvanCodes 发布时间：2025年5月1日🫡 专栏：Java教程大家好！👋 还记得我们上次聊的数组 (Array) 吗？它很基础，性能也不错，但有个致命的缺点：长度一旦定…...

编程日记 2025/5/8 11:04:15

Python 数据智能实战 (6)：用户评论深度挖掘

写在前面 —— 从繁杂评论到精准洞察：主题发现与情感趋势分析，驱动产品优化与体验提升在上篇内容中，我们学习了如何利用 LLM 提升用户分群的精度，以及如何超越传统购物篮分析，挖掘商品间的语义关联。今天，我们将聚焦于电商领域价值密度最高的非结构化数据之一——用…...

编程日记 2025/5/6 20:07:49

podman/docker国内可用的docker镜像源（2025-05）

一、添加Docker国内镜像 1、修改 /etc/docker/daemon.json 设置 registry mirror，具体命令如下: sudo vim /etc/docker/daemon.json <<EOF {"registry-mirrors": ["https://docker.1ms.run","https://docker.xuanyuan.me",&q…...

编程日记 2025/5/6 15:01:38

机器人--底盘

机器人底盘底盘是机器人传感器和机器人主机的载体，也是移动机器人的基本形式。移动机器人通常可以采用轮式和足式进行移动。也就是机器人底盘可以分为轮式底盘和足式底盘。足式底盘控制复杂，这里只讨论轮式底盘。底盘运动学模型轮式机器人底盘按…...

编程日记 2025/5/6 17:21:58

Seata服务端同步提交事务核心源码解析

文章目录前言一、doGlobalCommit（同步提交）2.1、closeAndClean()2.2、changeGlobalStatus2.3、doGlobalCommit2.3.1、findGlobalSession 总结前言本篇介绍Seata服务端TC如何驱动RM提交事务。一、doGlobalCommit（同步提交） doG…...

编程日记 2025/5/6 15:48:35

2025五一杯B题五一杯数学建模思路代码文章教学: 矿山数据处理问题

完整内容请看文章最下面的推广群问题1. 根据附件1中的数据和，建立数学模型，对数据A进行某种变换，使得变换后的结果与数据尽可能接近。计算变换后的结果与数据的误差，并分析误差的来源（如数据噪声、模型偏差等&#xf…...

编程日记 2025/5/8 22:45:52

C++11新特性_自动类型推导

decltype 和 auto 均为 C 里用于类型推导的关键字，不过它们在使用方式、推导规则和应用场景上存在显著差异。下面为你详细介绍它们的区别： 1. 推导依据 auto：它依据变量的初始化表达式来推导类型。也就是说，auto 定义的变量必须有…...

编程日记 2025/5/2 10:34:10

【AI论文】ReasonIR：为推理任务训练检索器

摘要：我们提出了ReasonIR-8B，这是第一个专门针对一般推理任务进行训练的检索器。现有的检索器在推理任务上表现出的收益有限，部分原因是现有的训练数据集侧重于与直接回答它们的文档相关的简短事实查询。我们开发了一个合成数据生成管道&am…...

编程日记 2025/5/2 10:33:08

嵌入式AI还是一片蓝海

发现其实还是挺多人关注嵌入式和人工智能交叉领域的，随便一个问题，浏览量就27万了，但是这方面的内容确实少得可怜……所以干脆我自己来补点干货。推荐一本最近很热门的新书——《边缘人工智能：用嵌入式机器学习解决现实问题》。 …...

编程日记 2025/5/7 0:41:13

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（13）：ておきますています＆てあります

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（13）： ておきます &ています　＆　てあります。 1、前言（1）情况说明（2）工程师的信仰 2、知识点（1）&#x…...

编程日记 2025/5/2 10:32:05

CMake管理外部依赖的模块

在 CMake 中，FetchContent 和 ExternalProject 都是管理外部依赖的模块，但它们的设计目标、使用场景和执行时机有本质区别。以下通过对比表格、代码示例和场景分析详细说明它们的区别。核心区别对比表特性FetchContentExternalProject执行阶段配置阶…...

编程日记 2025/5/5 14:42:00

[计算机科学#7]：CPU的三阶段，取指令、解码、执行

【核知坊】：释放青春想象，码动全新视野。我们希望使用精简的信息传达知识的骨架，启发创造者开启创造之路！！！ 内容摘要：本文详细介绍了CPU的工作原理，包括其结构…...

编程日记 2025/5/5 16:58:29

向量数据库和关系型数据库的区别，优点，缺点和典型应用场景

向量数据库与关系型数据库的全面对比向量数据库和关系型数据库是两种截然不同的数据管理系统，各自针对特定的数据模型和查询模式进行了优化。随着人工智能和大数据技术的发展，向量数据库作为新兴的数据库类型，在处理非结构化数据方面展现出…...

编程日记 2025/5/2 10:30:00

《跨越边界：探索跨端框架中通用状态管理方案设计》

一款应用往往需要在多个终端，如Web、移动端、桌面端等同时运行，以满足用户多元化的使用场景。在这复杂的跨端开发领域中，状态管理堪称关键枢纽，直接关乎应用的性能、稳定性以及开发与维护的效率。如何设计一套通用的状态管理方案&…...

编程日记 2025/5/9 14:28:20

PHP之CURL通过header传参数及接收

一、传参数之冒号注意一点，这里的header数据不是KV结构，而是一个一维数组。看清楚，注意一点，是这样的结构： $ch curl_init(); $headers [X-Custom-Header: value123,Authorization: Bearer your_token_here // …...

编程日记 2025/5/10 0:27:48

【C++】brpc安装

brpc安装教程环境：Ubuntu24.04 1 简单安装即安装到系统环境下，依赖也是依赖apt安装。官方参考教程依赖准备安装依赖： sudo apt-get install -y git g make libssl-dev libgflags-dev libprotobuf-dev libprotoc-dev protobuf-com…...

编程日记 2025/5/9 2:59:11

从0开始的c++知识讲解之字符串（1）

作者作为新手，对于知识的讲解也是边输出内容也是边学习，如有缺陷，请多海涵，但同样，我会帮助你从新手视角看到新手的疑惑，并帮助你解决此疑惑一，开宗明义，立意先行 string在C里有可…...

编程日记 2025/5/2 10:22:42

Linux 第六讲 --- 工具篇（一）yum/apt与vim

前言： 经过前五讲对Linux基础指令与权限系统的系统学习，相信你已经能在命令行中自如地穿梭于文件丛林，精准调配权限密钥。但真正的Linux玩家，绝不会止步于基础操作的重复劳作。从今天起，我们将打开Linux的"瑞士…...

编程日记 2025/5/2 10:21:38

xml 和 yaml 的区别

XML 和 YAML/YML 是两种常用的数据序列化格式，用于存储和读取结构化数据。以下是它们的核心区别和使用方法： 1. 格式特性对比特性XMLYAML/YML语法复杂度标签嵌套，结构严格缩进分层，更简洁可读性较低（冗余标签&#…...

编程日记 2025/5/6 12:35:17

1.67g 雨晨 22635.5305 Windows 11 企业版 23H2 极速增强版

五一特别制作 （主要更新简述） 全程由最新YCDISM2025装载制作 1、可选功能： 添加： Microsoft-Windows-LanguageFeatures-Basic-en-us-Package Microsoft-Windows-LanguageFeatures-OCR-en-us-Package 2、功能增强&a…...

编程日记 2025/5/2 10:20:34

【C++】类和对象（中）——默认成员函数详解（万字）

文章目录上文链接类的默认成员函数1. 构造函数(1) 什么是构造函数(2) 构造函数的使用 2. 析构函数(1) 什么是析构函数(2) 析构函数的使用(3) 小练习 3. 拷贝构造函数(1) 什么是拷贝构造函数(2) 拷贝构造函数的使用 4. 赋值运算符重载(1) 运算符重载(2) 运算符重载的简单应用(3…...

编程日记 2025/5/8 10:50:09

Ubuntu18 登录界面死循环 Ubuntu进不了桌面

今天碰到这个问题，真是把我恶心到了网上很多方法都不靠谱，最后我还是自己摸索出一个方法先进入终端开机后在登陆界面按下shift ctrl F1（或者F2，一直按）进入tty命令行终端登陆后输入(本人的用户名为hp&#xff…...

编程日记 2025/5/7 23:50:53

caffe适配cudnn9.6.0（ai修改代码踩坑）

caffe适配cudnn：https://github.com/dyc2424748461/caffe （测试一下，成没成，反正我看到它用gpu了😶） 因为突发奇想，想要玩easymocap，先是简单使用media跑通了一下，然后过…...

编程日记 2025/5/9 8:47:13

【MySQL数据库】视图

1，视图的基本介绍视图是一个虚拟表，其内容由查询定义。与真实表一样的是，视图包含带有名称的列和行数据；与真实表不一样的是，视图本身并不在数据库中存储数据。视图的数据变化会影响到基表，基表的数据变化…...

编程日记 2025/5/6 17:02:26

Linux日常使用与运维的AI工具全景调研：效率革命的终极指南

Linux日常使用与运维的AI工具全景调研：效率革命的终极指南引言：当Linux遇上AI，运维世界正在发生什么？作为一名Linux系统管理员，你是否还在为以下问题困扰：深夜被报警短信惊醒，却要手动排查复杂的系统故障？面对海量日志文件，像大海捞针一样寻找关键错误信息？重复…...

编程日记 2025/5/2 10:13:16

Linux——线程（3）线程同步

一、线程同步的引入通过上面的抢票系统我们发现，有的线程，进行工作（挂锁），当其马上结束工作（解锁），发现外面有很多线程在排队等着加锁执行任务，这个线程解锁后就立马给…...

编程日记 2025/5/6 15:17:04

Redis实现分布式锁

分布式锁是分布式系统中解决资源竞争问题的重要机制。Redis凭借其高性能和原子性操作，成为实现分布式锁的热门选择。本文将详细介绍如何使用Java和Redis实现分布式锁，并重点讲解如何通过Lua脚本保证锁操作的原子性。一、分布式锁的基本要求一个可靠的…...

编程日记 2025/5/8 20:23:44

JavaScript如何实现类型判断？

判断一个数据的类型，常用的方法有以下几种： typeofinstanceofObject.prototype.toString.call(xxx) 下面来分别分析一下这三种方法各自的优缺点 typeof typeof的本意是用来判断一个数据的数据类型，所以返回的也是一个数据类型。但是会遇到下…...

编程日记 2025/5/2 10:12:13

Spring MVC 与 FreeMarker 整合

以下是 Spring MVC 与 FreeMarker 整合的详细步骤，包含配置和代码示例： 1. 添加依赖在 pom.xml 中引入 Spring MVC 和 FreeMarker 的依赖（以 Maven 为例）：  <dependency><gr…...

编程日记 2025/5/5 14:13:29

设计模式简述（十五）观察者模式

观察者模式描述基本组件使用描述观察者模式，顾名思义就是一个对象观察着其他对象，一旦被观察的对象发生变化时，观察者对象也要做出相应动作。其中，被观察者持有观察者的引用。由观察者主动注入被观察者内（有点像…...

编程日记 2025/5/7 7:21:20

用手机相册教我数组概念——照片分类术[特殊字符][特殊字符]

目录前言一、现实场景1.1 手机相册的照片管理1.2 照片分类的需求二、技术映射2.1 数组与照片分类的对应关系2.2 数组索引与照片标签的类比三、知识点呈现3.1 数组的基本概念3.2 数组在编程中的重要性3.3 数组的定义与初始化3.4 数组的常见操作（增删改查&#xff…...

编程日记 2025/5/2 10:10:07

字符串格式漏洞-[第五空间2019 决赛]PWN5

之前其实也写了一篇，现在再来看。又有新的收获了，于是记录一下前置知识格式化字符串漏洞详解-CSDN博客讲得很清楚，我就不照猫画虎了实践 main函数首先先办法泄露我们输入的地址 from pwn import * elfpathlevel0 # ioprocess(elfp…...

编程日记 2025/5/8 17:18:06

数据结构学习之顺序表

在C语言学习到一定阶段之后，接下来我们就进入到了数据结构的部分内容。目录数据结构与线性表顺序表顺序表分类： 接下来我们要写一段代码实现动态顺序表。首先我们需要准备三个文件： 1.接下来我们要定义一个数据表 2.当创建号我们的…...

编程日记 2025/5/2 10:09:05

AWS CloudFront全球加速利器：解析出海业务的核心优势与最佳实践

对于寻求全球化发展的企业而言，AWS CloudFront凭借其强大的全球基础设施和边缘计算能力，成为加速出海业务的关键工具。本文将深入剖析CloudFront的核心优势，并探讨其如何助力企业突破跨境业务瓶颈，同时符合SEO优化策略&#xff0c…...

编程日记 2025/5/7 9:08:33

Flowable7.x学习笔记（十六）分页查询我的待办

前言我的待办具体区分为3种情况，第一个就是办理人指定就是我，我可以直接审批；第二种就是我是候选人，我需要先拾取任务然后再办理；第三种是我是候选组，我需要切换到指定的角色去拾取任务再办理。如果任务已…...

编程日记 2025/5/6 17:10:56

Annotate better with CVAT

WIN10 配置标注环境 WSL + Docker Desktop 安装手册 https://docs.cvat.ai/docs/administration/basics/installation/ hebing@hello:~$ docker images REPOSITORY TAG IMAGE ID CREATED SIZE cvat/ui …...

编程日记 2025/5/7 7:56:04

QML Image 组件详解

目录引言相关阅读QML Image元素基础知识项目结构示例解析1. 本地资源图像加载2. 网络图像加载3. 图像填充模式应用主结构总结下载链接引言本文将介绍QML中Image元素的基本用法和关键特性，包括加载本地资源图像、处理网络图像、以及调整图像的填充模式。通过一…...

编程日记 2025/5/2 10:05:58

BOFZ 緩衝區溢出shell脚本檢測工具

地址:https://github.com/MartinxMax/bofz BOFZ BOFZ 是一款簡單的緩衝區溢出掃描器，旨在檢測指定可執行文件中的緩衝區溢出漏洞。此工具可用於快速測試應用程序或二進制文件中是否存在常見的安全缺陷，特別是那些由於對用戶輸入處理時邊界檢查不當而引…...

编程日记 2025/5/2 10:05:57

【Dify系列教程重置精品版】第五章：Dify配置Ollama

上一章我们在Dify上尝试配置了“月之暗面”。这一章我们在Dify上配置另一个模型“Ollama”。什么是ollama呢？简单来说：它允许用户在个人计算机或服务器上快速部署和管理多种开源大语言模型，如 Llama3、Phi3、Gemma2 等，而无需依赖昂贵的云服务或专业的技术背景。反正就是…...

编程日记 2025/5/8 15:50:43

RISC-V AIA SPEC学习（四）

第五章 Interrupts for Machine andSupervisor Levels 核心内容 1.主要中断类型与默认优先级：定义了机器级别(M-level)和监管者级别(S-level)的标准中断类型（如MEI、SEI、MTI等）。默认优先级规则：本地中断（如软件/定时器）优先级高于外部中断，RAS事件（如低/高…...

编程日记 2025/5/2 10:04:53

Leetcode刷题报告2——双指针法

文章目录前言[15. 三数之和](https://leetcode.cn/problems/3sum/)题干题解知识点总结 [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/)题干题解前言这部分总共是4道题，我就挑两道比较典型的题写一下博客吧。双指针法的核心思路是通过合理的…...

编程日记 2025/5/7 14:55:14

相关文章：