📋 ACGO社区帮助手册 🌟 站务汇总 * 站务汇总 🏆 赛事信息 * 巅峰排行榜规则介绍 * 排位分机制揭秘 🗨️ 讨论区指南 * 发帖规范 * 删帖原因 团队招募帖子通常不应发布在“学习讨论”板块； 发布无意义内容； 发布违反社区规范的内容； 发布格式混乱，难以阅读的题解，不符合题解规范的题解。 📘 格式手册 * LaTeX数学公式语法 * Markdown语法教程 🤔 提问与解答 * 提问的智慧 * 题解编写技巧 🤖 AC助手使用指南 * AC助手的正确食用方法 🧠 知识点精华贴 * 知识点精华贴

赛时10min 切了 生成用了9min，改马蜂1min

前言： 本文涵盖KMPKMPKMP算法的详细步骤，大家有什么建议可以在评论区说哦！ 加精啦！！！感谢AC君赞助！！！ 竟然榜7了！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广告： 求加团！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 目录（CONTENTS）： > > > > 第一部分：导言 > > > > > > 第二部分：什么是 KMP 算法 > > > > > > 第三部分：KMP 算法的核心概念与预处理 > > > > > > 第四部分：KMP 算法的匹配过程与实现 > > > > > > 第五部分：刷题时光 > > > > > > 第六部分：常见踩坑点与避坑指南 > > > > > > 第七部分：常见问题与注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第一部分：导言: 在字符串处理场景中，我们经常需要解决 “模式匹配” 问题 —— 比如从一篇文章里找某个关键词、在日志中匹配特定指令，这时候最直接的思路是 “暴力匹配”：用模式串的每个字符依次对比主串的对应位置，不匹配就回溯主串重新开始。 但暴力匹配效率极低，比如主串是"AAAAA...A"（1000 个 A），模式串是"AAAB"，每次匹配到最后一个字符才失败，主串频繁回溯导致时间复杂度达到O(N*M)（N 为主串长度，M 为模式串长度）。 为此，我们需要更高效的算法 ——KMP 算法。它通过预处理模式串生成 “部分匹配表”（PMT），避免主串回溯，将时间复杂度优化到O(N+M)，是字符串匹配的经典高效方案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：什么是 KMP 算法： KMP 算法由 KNUTH、MORRIS 和 PRATT 三位科学家共同提出，核心思想是利用模式串自身的前缀后缀匹配信息，在匹配失败时让模式串 “少后退”，从而跳过不必要的对比步骤。 核心问题：为什么暴力匹配效率低？ 假设主串为S = "ABCABDABCAB"，模式串为P = "ABCAB"： > ·暴力匹配时，前 4 个字符 "ABCA" 均匹配，第 5 个字符 S [4] = 'X'（此处替换为与 'B' 不匹配的字符，如 'X'）与 P [4] = 'B' 不匹配，此时主串会回溯到 S [1]，模式串回到 P [0] 重新开始。 > ·但观察模式串"ABCAB"，其前 4 个字符"ABCA"的前缀"A"和后缀"A"是最长匹配的（长度 1）。这意味着主串中S[3] = 'A'（对应模式串P[3] = 'A'）其实可以直接与模式串的P[1]继续匹配，无需回溯主串。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分：KMP 算法的核心概念与预处理： 在学习 KMP 的实现前，必须掌握两个核心概念：前缀后缀和部分匹配表（PMT）。 3.1. 前缀与后缀： > ·前缀：字符串中除最后一个字符外，所有以第一个字符开头的连续子串。例："ABCAB"的前缀为["A", "AB", "ABC", "ABCA"]。 > ·后缀：字符串中除第一个字符外，所有以最后一个字符结尾的连续子串。例："ABCAB"的后缀为["B", "AB", "CAB", "BCAB"]。 > ·最长公共前缀后缀（LCP）：前缀和后缀中长度最长的相同子串。例："ABCAB"的 LCP 为"AB"，长度为 2。 3.2. 部分匹配表（PMT）： 部分匹配表（也称NEXT数组）是 KMP 的核心，它存储了模式串中每个位置的前缀子串的 LCP 长度。 > ·下标：模式串的字符位置（从 0 开始）。 > ·值：该位置前的前缀子串（即P[0..I-1]）的 LCP 长度。 如何构建 PMT（以模式串P = "ABCAB"为例）： 模式串字符 p[0] = 'A' p[1] = 'B' p[2] = 'C' p[3] = 'A' p[4] = 'B' 前缀子串 空串 "A" "AB" "ABC" "ABCA" LCP 长度 0 0 0 1 2 PMT 值 0 0 0 1 2 构建 PMT 的代码实现： 核心逻辑：用双指针I（指向后缀末尾）和J（指向前缀末尾）遍历模式串，通过对比字符更新 LCP 长度： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第四部分：KMP 算法的匹配过程与实现： 有了 PMT，KMP 的匹配过程就非常清晰了：用两个指针分别遍历主串S和模式串P，匹配失败时通过 PMT 调整模式串指针，主串指针始终不回溯。 匹配步骤 1.初始化主串指针I = 0，模式串指针J = 0，并构建模式串的 PMT。 2.遍历主串： > ·若S[I] == P[J]：两个指针同时后移（I++，J++）。 > > ·若S[I] != P[J]： > > > ·若J > 0：通过 PMT 将J调整为PMT[J-1]（利用前缀后缀匹配信息跳过无效对比）。 > > > > ·若J == 0：主串指针后移（I++），模式串从开头重新匹配。 3.当J == P.SIZE()时，说明模式串完全匹配，返回匹配的起始位置（I - J）；遍历结束未匹配则返回 - 1。 完整代码实现： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第五部分：刷题时光： 例题 1：LEETCODE 28. 找出字符串中第一个匹配项的下标 题目大意：给你两个字符串HAYSTACK（主串）和NEEDLE（模式串），请返回NEEDLE在HAYSTACK中首次出现的下标。如果NEEDLE不是HAYSTACK的一部分，则返回-1。 解题思路：直接套用 KMP 算法模板，核心是构建 PMT 并执行匹配逻辑。 完整代码： 例题 2：查找模式串在主串中的所有匹配位置 题目大意：读入主串S和模式串P，输出P在S中所有出现的起始下标，若未匹配则输出 “无匹配”。 解题思路：在 KMP 匹配中，当J == M（匹配成功）时，不直接返回，而是通过 PMT 调整J（J = PMT[J-1]），继续查找后续匹配。 核心代码片段： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第六部分：常见踩坑点与避坑指南： KMP 算法的逻辑看似清晰，但在编码和理解过程中极易陷入细节陷阱，以下是高频踩坑点及解决方法： 1. PMT 构建：用 “IF” 代替 “WHILE” 回溯 J，导致 LCP 计算错误： 坑点描述： 构建 PMT 时，当P[I] != P[J]，新手常误用IF语句单次回溯J（如IF (J>0) J=PMT[J-1]），而非WHILE循环，导致无法找到最长的有效前缀后缀。 反例代码（错误） 问题分析： 以模式串P = "ABABAC"为例： > ·当I=4（P[I]='A'）、J=3（P[J]='B'）时，P[I] != P[J]，需回溯J到PMT[2] = 2（P[2]='A'）。此时P[4]='A' == P[2]='A'，J应更新为 3。 > ·若用IF，仅回溯一次就停止；若P[J]仍不匹配（如更复杂的模式串），会导致 LCP 长度计算偏短，后续匹配出错。 避坑方案： 必须用WHILE循环回溯J，直到J=0或P[I] == P[J]，确保找到最长的公共前缀后缀： 2. 匹配时：主串指针回溯，违背 KMP 核心逻辑： 坑点描述： 受暴力匹配思维影响，在S[I] != P[J]时，不自觉地让主串指针I回溯（如I = I - J + 1），导致时间复杂度退化为O(N*M)，失去 KMP 的效率优势。 反例代码（错误） 问题分析： KMP 的核心优化是 “主串不回溯”，所有调整仅针对模式串指针J。主串指针I一旦后移，就不再退回，这是保证O(N+M)复杂度的关键。 避坑方案： 牢记：匹配过程中主串指针I只做自增，绝不回溯。所有匹配失败的调整都通过修改J实现。 3. 边界处理：忽略模式串为空或长度大于主串的情况 坑点描述： 编码时未考虑极端边界场景，如模式串P为空、P.SIZE() > S.SIZE()，导致数组越界或返回错误结果。 反例代码（错误） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第七部分：常见问题与注意事项： 1.PMT 与 NEXT 数组的区别：有些资料中NEXT数组是 PMT 的 “右移 + 1” 版本（如NEXT[0] = -1），本质逻辑一致，只是实现时指针调整方式略有不同，本文采用原始 PMT 定义更易理解。 2.模式串为空的处理：根据题目要求，通常模式串为空时返回 0（匹配开头）或空列表。 3.字符类型适配：KMP 算法适用于所有可比较的字符类型（如大写字母、小写字母、数字），无需修改核心逻辑。 4.PMT 构建的易错点：当P[I] != P[J]时，必须用WHILE循环回溯J（而非IF），确保找到最长的有效前缀后缀。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 尾声： > 特别鸣谢： > > > 排版： @AC是最好的 > > > > 标题：@‮༺དༀ༒∞░∞༒ༀཌ༻ > > > > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻ > > > > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻ 创作不易，给一个赞吧，求求了

本篇讲解哈希算法，这是一种在很多领域都有运用的算法。 > 目录 > > > > 1.简介 > > > > > > 2.关键性质 > > > > > > 3.核心思想 > > > > > > 4.单哈希算法 > > > > > > 5.双哈希算法 > > > > > > 6.无符号长整型溢出法 PART 1. 简介 哈希算法在编程竞赛中的主要应用是把一个字符串映射为一个数字（通常会取模）来把O(n)O(n)O(n)的字符串比较问题转化为O(1)O(1)O(1)的数字比较（当然预处理不是O(1)O(1)O(1)的）。 PART 2. 关键性质 哈希算法主要有以下性质 1. 确定性 * 相同的输入必定产生相同的哈希值（也是哈希算法的基础） 2. 高效性 * 计算哈希值的过程应该很快 3. 雪崩效应 * 输入的微小变化会导致输出的巨大差异 * 例如"aelloaelloaello"和"hellohellohello" 的哈希值应该完全不同 4. 抗碰撞性（这个指标是用来判定哈希冲突的） * 弱抗碰撞性：给定一个输入，很难找到另一个不同的输入产生相同的哈希值 * 强抗碰撞性：很难找到任意两个不同的输入产生相同的哈希值 PART 3. 核心思想 哈希算法的核心思想在于，将字符串的每个字符对应成0~25的数字，再将整个字符串映射为一个kkk进制数（kkk通常取128128128）模一个大质数（比如1e91e91e9、998244353998244353998244353）。 具体实现不难，只需预处理128128128的幂次就可以轻松实现。 PART 4. 单哈希算法 单哈希算法即只用一个数作为模数。 实现并不难，模板代码就不给了，给出一道例题 PART 5. 双哈希算法 这是我们重点讲解的算法。 要想学习双哈希算法我们首先得了解—— 哈希冲突\HUGE 哈希冲突哈希冲突 相信很多读者会发现：哈希算法是基于映射和取模的，那岂不是很好hackhackhack？只要构造两个取模后相等的字符串不就好了？没错，这就是哈希冲突，双哈希算法就是用以解决哈希冲突的。 那么我们如何解决哈希冲突呢？很粗暴，就是用两个不同的模数来判断，如果两个字符串所映射的数字模两个数都相等，那么他们大概率就是相等的。 这时候，聪明的同学就说了，主包主包，那还是可以hackhackhack啊？大家大可放心，到现在还没有人成功hackhackhack掉双哈希（bzojbzojbzoj上就有一道这样的题，一直到它倒闭都没人做出来），因为如果有这样的数据，字符串会长到不可想象，所以双哈希是绝对可靠的。 就算不可靠你可以再模一个，自创三哈希 > 注：一个实用技巧，哈希在实战中常常使用前缀的形式，详见后面的代码。 下面给出一道例题 代码： 我在其中封装了两个哈希结构，不会封装的也可以分开写。 PART 6. 无符号长整型溢出法 双哈希固然好用，但是实现非常困难也没多困难，所以，我们隆重推出懒人写法—— 无符号长整型法，即unsignedunsignedunsigned longlonglong longlonglong。 这个算法基于无符号长整型溢出后自动取模的特点，但是有小概率被卡CSP被卡别怪我 还是给一道例题 代码： 大概是史上最短创作计划了，萌新有什么看不懂的可以在评论区留言，也欢迎大佬给出珍贵的建议，@AC君求精。

原文：数据结构map：解决桶排序问题的另一方式 （不是转载，我自己写的！帮忙点个赞吧！） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 作为C++的进阶者，相信各位对于桶排序并不陌生。然而，对于大多数进阶者来说，桶排序可以用一种STL库中的数据结构来替代。这就是我们今天要说的map。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 概念 map是一种关联式容器，是STL库中的一个重要数据类型，由一个键和一个值相对应构成。可以通过键查找到值，但是不可以由值找键！map的查找实现是以红黑树（一种二叉搜索树）为依托的，同时在插入数据时还会自动重载operator[]。 map的出现成为对桶排序算法的优化，由于其自动排序的特性和方便的函数操作收到了众多oier的喜爱。最初，由于指针的开发不全面，map的特性和好处尚不明显；后来auto的出现大大提升了STL库的受欢迎程度，map的遍历也因此变得更加方便快捷。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 使用 与其它STL库数据结构不同的是，map的内容共有两个，分别是键和值，统称为键值对。下面是map的创建方法：map<key,value> mp; key为键，只能出现一次；value为值，可以出现多次。（即为同键同值，同值异键）mp为库的名称，可以根据情况自行选择。 在这里声明一下，map与multimap是两个不同的数据结构，multimap具有的特点之一是可以有相同的键。若有想要了解的请戳这里。 言归正传，map可以代替桶排序是因为它也可以对数据进行统计，键值的对应让值的更改可以通过键来完成。下面给出map的插入与删除操作方式： > 插入：map[key] = value（对于int类型的值也可以使用自增和自减操作） > 删除：mp.erase(key)（该操作会将key键的值设置成0，程序会将map的大小减一） > 清空：mp.clear() erase的更多操作请看此图： 还有更多查询的函数，本人已经整理成一张表了，如下： 函数名 返回值 时间复杂度 count(x) 返回容器内键为 x 的元素数量 O(1) find(x) 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 end() O(logn) lower_bound(x) 返回指向首个不小于给定键的元素的迭代器 O(logn) upper_bound(x) 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 end() O(logn) empty() 返回容器是否为空 O(1) size() 返回容器内元素个数 O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题 题目名称 新建文件夹（1） 题目链接 ATcoder入口 ACGO入口 洛谷入口 （建议通过ATcoder、ACGO答题，因为洛谷搬运自ATcoder及ACGO，数据点不保证强度且数据测试点较少。） 思路分析 STL库模板题。本题我们可以通过STL模板库中的map来解决。新建一个map后，将类型设置为<string,int>，这样就可以通过文件夹名称查询到次数。在计数结束后，只需要判断前面是否出现名称为X的文件，如果有就输出X-1，如果没有就输出0。 代码解析 C++代码： Python代码： 时间复杂度：O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 练习 入门题目：（入门）好串、（普及-）丢失的数据 进阶题目：（普及+/提高）数字游戏、（省选/NOI-）火星人 （以上题目均出自ACGO） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参考文献：oi-wiki 关联式容器 文章创作不易，麻烦各位oier点个赞支持一下吧！（我绝对不会告诉你这是在机场写的）

水绿，拆位就行了，赛时20min切了

感谢AC君加精\tiny 感谢AC君加精感谢AC君加精 > UPD 9.28，应评论区大佬建议，增加了关键代码的注释。 本篇文章讲解图论算法，包括最短路、最小生成树、并查集和基础的LCALCALCA MARKDOWNMARKDOWNMARKDOWN原码5318字，最终展示4000左右。 大家请坐稳，我们马上开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 1 最短路算法 最短路算法是图论中最基础的方法，在各大比赛中都有涉及，本篇将会提到4种最短路算法。 一、定义 最短路问题即求一个带权图中两个节点的最短的路径。 二、DIJKSTRADIJKSTRADIJKSTRA算法 1.简介 这是图论中最常用的最短路算法，由荷兰计算机科学家EdsgerW.DijkstraEdsger W. DijkstraEdsgerW.Dijkstra于195619561956年提出，其核心思想是贪心和广度优先搜索。它解决的是单源最短路问题。 2.核心思想 DijkstraDijkstraDijkstra算法的核心在于维护一个 distdistdist 数组， dist[i]dist[i]dist[i] 表示从起点到 iii 号点的最短路。 3.适用范围 非负权图，DijkstraDijkstraDijkstra算法每个点只松弛一次的特性决定了其无法解决负权问题。 4.朴素DIJKSTRADIJKSTRADIJKSTRA算法 * DijkstraDijkstraDijkstra算法将节点分为两类： 1. 已确定节点：已经找到从起点到该节点的最短路径的节点集合。 2. 未确定节点：尚未找到最短路径的节点集合。 * 算法流程： 1. 每次从 “未确定节点” 集合中，选择一个 距离起点最近 的节点。 2. 将其加入 “已确定节点” 集合。 3. 松弛 这个新确定节点的所有邻居。 * 松弛操作（也是该算法最重要的思想）： 检查对于新确定节点 uuu 的每一个邻居 vvv，如果从起点 sss 先到 uuu，再从 uuu 到 vvv 的路径距离，比之前已知的到 vvv 的距离更短，那么就更新 vvv 的距离。 * 核心代码： * 完整代码： * 时间复杂度：O(n2+m)O(n^2+m)O(n2+m)（一般写作O(n2)O(n^2)O(n2)） * 空间复杂度：O(n+m)O(n+m)O(n+m) 5.堆优化DIJKSTRADIJKSTRADIJKSTRA算法 * 区别于朴素做法的枚举每个可能松弛的节点，堆优化算法使用堆找到目前最近（最可能松弛）的节点。 * 代码： * 时间复杂度：O(mlogn)O(mlogn)O(mlogn) * 空间复杂度：O(n+m)O(n+m)O(n+m) * 注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。\color{red}{注意在稠密图中，堆优化算法会退化为O(n^2logn),此时应使用朴素算法。}注意在稠密图中，堆优化算法会退化为O(n2logn),此时应使用朴素算法。 6. 练习 三、FLOYDFLOYDFLOYD算法 1.简介 FloydFloydFloyd算法是一种基于dpdpdp的思想，是学生们最喜欢的一种基础最短路算法也是最慢的（竞赛中不常用） 2.核心思想 从节点 iii 到节点 jjj 的最短路径，无非有两种可能： 1. 直接从 iii 到 jjj。 2. 从 iii 经过某些中间节点 kkk 再到 jjj。 FloydFloydFloyd算法不断尝试和比较这些可能性，逐步优化最短路径的估计值（这也是该算法较慢的原因）。 3.适用范围 FloydFloydFloyd不适用于存在负权回路的图中。 4.FLOYDFLOYDFLOYD算法实现 * 状态定义： d[k][i][j]d[k][i][j]d[k][i][j]：表示从节点 iii 到节点 jjj，仅使用 1,2,⋯ ,k1, 2, \cdots, k1,2,⋯,k 号节点作为中间节点的所有可能路径中的最短路径长度。 * 状态转移方程： 对于每一个中间节点 kkk，我们检查对于每一对 (i,j)(i, j)(i,j)，是否存在一条更短的路径： d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]) d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j]) * 这个方程的含义： d[k−1][i][j]d[k-1][i][j]d[k−1][i][j]：不使用 kkk 作为中间节点，iii 到 jjj 的最短路径。 d[k−1][i][k]+d[k−1][k][j]d[k-1][i][k] + d[k-1][k][j]d[k−1][i][k]+d[k−1][k][j]：使用 kkk 作为中间节点，路径分解为 iii -> kkk 和 kkk -> jjj 两段，这两段路径只使用前 111 到 k−1k-1k−1 号节点作为中间节点。 * 取这两种情况的最小值。 * 代码（空间优化版）： * 时间复杂度：O(n3)O(n^3)O(n3) * 空间复杂度：O(n2)O(n^2)O(n2) 5. 练习 四、BELLMANBELLMANBELLMAN-FORDFORDFORD算法 1.简介 BellmanBellmanBellman-FordFordFord算法是另一种单源最短路算法，价值在于可以解决负权（回路）问题。 2.核心思想 BellmanBellmanBellman-FordFordFord算法的思想非常直接： 最短路径最多经过 n−1n-1n−1 条边。 如果一条从源点 sss 到终点 ttt 的最短路径经过了超过 n−1n-1n−1 条边，那么它必定包含一个环。如果是正环或零环，可以移除它得到更短的路径；如果是负环，则不存在最短路径。 基于这个思想，通过松弛操作对图中的所有边进行 n−1n-1n−1 轮遍历。每一轮遍历都尝试用一条边来更新和优化当前已知的最短距离。经过 n−1n-1n−1 轮后，理论上所有可能的最短路径都已经被找到。这时执行一轮松弛操作，还能有路径被更新，则证明图中存在负权回路。 3.适用范围 BellmanBellmanBellman-FordFordFord算法适用于所有情况 4.BELLMANBELLMANBELLMAN-FORDFORDFORD算法实现 * 初始化： 1. 将dist[s]dist[s]dist[s] 设为 000。 2. 将所有其他节点的 distdistdist 值初始化为 1e91e91e9。 * 进行 n−1n-1n−1 轮松弛： 1. 对每一轮，遍历图中的所有 mmm 条边。 2. 对于每条边 (u,v,w)(u, v, w)(u,v,w)，执行松弛操作： * 核心代码： * 如果需要检查负权回路，再额外进行一次对所有边的遍历（即第 nnn 轮松弛），如果发现任何一条边 还能进行松弛操作，就可以得出结论：图中存在从源点 sss 可达的负权回路。 * 注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。\color{red}{注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。}注意：每一轮松弛的顺序可能会影响效率，但不影响最终结果的正确性。 * 完整代码： * 时间复杂度：O(nm)O(nm)O(nm) * 空间复杂度：O(n+m)O(n+m)O(n+m) 5. 练习 五、SPFASPFASPFA算法 1.简介 SPFA（ShortestPathFasterAlgorithm）SPFA（Shortest Path Faster Algorithm）SPFA（ShortestPathFasterAlgorithm）是对于BellmanBellmanBellman-FordFordFord的队列优化版本，在随机图中时间更优，但容易被卡。 2.核心思想 我们发现，BellmanBellmanBellman-FordFordFord算法中，并不是每一次松弛操作都会有效，只有那些在前一轮松弛中成功更新了最短路径值的点，才有可能引领下一次有效的松弛。 SPFASPFASPFA 对此进行了关键优化： 使用一个队列来维护有可能引起松弛操作的点。只有当某个点 uuu 的最短距离 dist[u]dist[u]dist[u] 被更新变小了，才说明它的出边有可能使其邻居 vvv 的 dist[v]dist[v]dist[v] 也变小。这时，我们才将 uuu 放入队列，等待后续用它来松弛它的邻居。 这个过程避免了 BellmanBellmanBellman-FordFordFord中大量无用的松弛尝试，使其在平均情况下的时间复杂度远优于BellmanBellmanBellman-FordFordFord。 3.适用范围 SPFASPFASPFA适用于所有情况 4.SPFASPFASPFA算法实现 * 初始化： 1. 创建 distdistdist 数组，dist[s]=0dist[s] = 0dist[s]=0，其余为 INFINFINF。 2. 创建一个队列 qqq，将源点 sss 入队。 * 创建一个 in_queuein\_queuein_queue数组，标记节点是否已在队列中，防止重复入队。初始时，in_queue[s]=Truein\_queue[s] = Truein_queue[s]=True。 * (可选，用于检测负环) 创建一个 countcountcount 数组，记录每个节点的入队次数，初始为 000。 * 主循环：当队列不为空时 1. 从队首弹出一个节点 uuu，并标记 in_queue[u]=Falsein\_queue[u] = Falsein_queue[u]=False。 2. 遍历 uuu 的所有出边 。 3. 尝试对边 (u,v)(u, v)(u,v) 进行松弛操作。 * 代码： * 平均时间复杂度：O(km)O(km)O(km) 其中kkk是个很小的常数 * 最坏时间复杂度：O(nm)O(nm)O(nm) 在一些特殊数据，比如网格图中，会退化为BellmanBellmanBellman-FordFordFord * 空间复杂度：O(n+m)O(n+m)O(n+m) 六、小结 算法 DijkstraDijkstraDijkstra BellmanBellmanBellman-FordFordFord SPFASPFASPFA FloydFloydFloyd 类型 单源最短路径 单源最短路径 单源最短路径 多源最短路径 策略 贪心 动态规划 队列优化 动态规划 时间复杂度 O(mlogn)O(m log n)O(mlogn) O(nm)O(nm)O(nm) O(km)O(km)O(km) O(n3)O(n^3)O(n3) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) 负权边 ❌ ✅ ✅ ✅ 负环检测 ❌ ✅ ✅ ❌ 适用场景 非负权图 负权图 随机图 n<500n<500n<500 最佳情况 非负权图 负权图 随机图 n<500n<500n<500 最坏情况 无，均可用对应优化 稠密图 特殊图，例如网格图 小数据，大规模查询 实现难度 中等 中等 较难 简单 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 2 并查集 并查集是图论中一种基础算法，是最小生成树等算法的基础，本篇将会提到3种并查集。 一、定义 并查集是一种用于管理元素分组情况的数据结构。 二、朴素版 1.简介 并查集高效地支持以下两种操作： * 合并：将两个元素所在的集合合并为一个集合。 * 查找：查询某个元素是否在同一集合。 2.核心思想 并查集的核心思想在于用多棵树来表示集合。森林中的每一棵树代表一个集合，树中的每个节点对应一个元素，树的根节点就是这个集合的“代表”。 3.算法流程 * 初始化： 一开始，我们拥有nnn个元素。通常我们用一个数组 parentparentparent 来表示每个元素的父节点。 初始化时，每个元素都是自己的父亲，即每个元素自成一个集合，自己是自己那棵树的根。 * 查找 即查找元素 xxx 所在集合的根节点。方法很简单：不断地通过 parentparentparent 数组向上查找，直到找到那个父节点指向自己的元素（即 parent[x]=xparent[x] = xparent[x]=x），它就是根节点。 * 合并 即将元素 xxx 和元素 yyy 所在的两个集合合并成一个集合，主要有两个步骤： 1. 找到 xxx 的根节点 rootx=find(x)rootx = find(x)rootx=find(x) 和 yyy 的根节点 rooty=find(y)rooty = find(y)rooty=find(y)。 2. 如果 rootx=rootyrootx=rootyrootx=rooty，说明它们本来就在同一个集合里，无需合并。否则将其中一棵树挂到另一棵树的根节点下面。即让 parent[rootx]=rootyparent[rootx] = rootyparent[rootx]=rooty。 4.代码实现 * 单次操作时间复杂度：最坏O(n)O(n)O(n) * 空间复杂度：O(n)O(n)O(n) 5. 练习 三、按秩合并 1.简介 在朴素算法中，我们不难发现，在特殊数据下，树会退化为一条链，时间会退化为O(n)O(n)O(n)，无法满足需求，于是按秩合并应运而生。 2.核心思想 我们使用一个额外的数组 rankrankrank 来记录每个根节点所代表的树的“高度”的估计值（这就是秩）。 初始时，每个元素都是根节点，自己构成一棵高度为 000 的树，所以 rank[i]=0rank[i] = 0rank[i]=0。 注意：我们只维护根节点的rank值，非根节点的rank值没有意义。\color{red}{注意：我们只维护根节点的 rank 值，非根节点的rank值没有意义。}注意：我们只维护根节点的rank值，非根节点的rank值没有意义。 3.算法流程 * 在合并两个根节点 rootxrootxrootx 和 rootyrootyrooty 时： 1. 比较它们的秩（rank[rootx]rank[rootx]rank[rootx] 和 rank[rooty]rank[rooty]rank[rooty]）。 2. 将秩较小的树挂到秩较大的树下。 * 注意：如果两棵树的秩相等：任意选择一方作为新的根，并将新根的秩加 111。 * 为什么相等时要加 111？ 想象两颗高度均为 hhh 的树。当它们合并时，新树的高度至少为 h+1h+1h+1（将一颗树挂到另一颗的根节点下，整个树的高度必然增加 111）。 4.代码实现 这段代码请由各位自行完成(doge)。 5. 还是这道 四、路径压缩 1.简介 路径压缩是并查集中一种非常重要的优化技术，它在查找中实施，可以显著提高并查集的效率。 2.核心思想&算法流程 朴素算法通过递归查找根节点，而路径压缩指的是在递归返回的过程中，将路径上每个节点的父节点直接设置为根节点，这样，整个路径被"压缩"了，所有节点都直接指向根。 3.代码实现 这是朴素的findfindfind 这是路径压缩的findfindfind 完整代码： 5. 还是这道 6.复杂度分析 * 时间复杂度：并查集的时间复杂度分析比较特殊，它不是一个简单的 O(logn)O(log n)O(logn) 或 O(n)O(n)O(n)，路径压缩的时间复杂度是由一个增长极其缓慢的函数——反阿克曼函数 α(n)α(n)α(n) 来描述。至于这个函数有多缓慢呢？在n≤265536n ≤ 2^{65536}n≤265536 时，α(n)≤5α(n) ≤ 5α(n)≤5。所以路径压缩并查集的单次操作一般认为是O(1)O(1)O(1)的。 * 空间复杂度：O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 3 最小生成树 最小生成树是图论中一种基础方法，考试中会出现很多变体，本篇将会提到两种最小生成树算法。 一、定义 生成树是一个无向连通图的子图。它必须包含原图的所有顶点，但只包含足够形成一棵树的边，并满足以下三个条件： * 是连通图：所有顶点都连接在一起。 * 无环：图中不存在任何环路。 * 边数 = 顶点数 - 111。 最小生成树 就是在一个带权连通无向图中，所有可能的生成树里，边的权重之和最小的那一棵（或那几棵）。 二、KRUSKALKRUSKALKRUSKAL算法 1.简介 KeuskalKeuskalKeuskal算法是基于边的一种最小生成树算法，也是竞赛中最常用的一种。 2.核心思想 从小到大选择不会形成环的边，直到连接所有顶点。 3.算法流程 * 排序：将图中所有的边按权重从小到大排序。 * 初始化：创建一个空的集合用于存放最小生成树的边。 * 遍历：按权重从小到大遍历每条边： * 如果当前边连接的两个顶点不在集合的同一个连通分量中（即加入这条边不会形成环），则将这条边加入集合。 * 如果会形成环，则跳过。 * 终止条件：当集合中的边数等于顶点数减111时，算法结束。 * 如何判断是否成环？ 我们通常使用并查集来高效地判断两个顶点是否属于同一个集合以及把两个点的集合合并。 4.代码实现 * 时间复杂度：O(mlogm)O(mlogm)O(mlogm) * 空间复杂度：O(n+m)O(n+m)O(n+m) 5. 练习 三、PRIMPRIMPRIM算法 1.简介 不同于KruskalKruskalKruskal算法，PrimPrimPrim算法是基于点的一种最小生成树算法，比较慢。 2.核心思想 从一个顶点开始，每次选择与当前树相连的权重最小的边，并扩展这棵树。 3.算法流程 * 初始化： 1. 随机选择一个顶点作为起点，加入最小生成树集合。 2. 维护一个数组 keykeykey，记录每个顶点到当前最小生成树的最小权重，初始值为无穷大（起点为000）。 3. 维护一个数组 parentparentparent，记录每个顶点是由哪条边连接进来的。 * 循环扩展： 1. 从未被选择的顶点中，选择一个 keykeykey 值最小的顶点 uuu，将其加入树中。 2. 遍历顶点 uuu 的所有邻接顶点 vvv，如果边 (u,v)(u,v)(u,v) 的权重小于 vvv 当前的 keykeykey 值，则更新 vvv 的 keykeykey 值为这个权重，并记录 parent[v]=uparent[v] = uparent[v]=u。 * 终止条件：所有顶点都被加入树中后，算法结束。parentparentparent 数组就定义了最小生成树的结构。 4.代码实现 * 时间复杂度：O(mlogn)O(mlogn)O(mlogn)（不用优先队列的朴素版是O(n2)O(n^2)O(n2)） * 空间复杂度：O(n+m)O(n+m)O(n+m) 四、小结 算法 KruskalKruskalKruskal PrimPrimPrim 对象 边 点 时间复杂度 O(mlogm)O(m log m)O(mlogm) O(mlogn)O(mlogn)O(mlogn) 空间复杂度 O(n+m)O(n+m)O(n+m) O(n+m)O(n+m)O(n+m) 适用场景 稀疏图 稠密图 数据结构 并查集 优先队列 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PART 4 LCALCALCA—最近公共祖先 这是一个在树中非常常见且重要的问题，是许多其他高级问题的基础。 一、定义 字面意思对于一棵有根树中的两个节点 ppp 和 qqq，它们的最近公共祖先被定义为同时是 ppp 和 qqq 的祖先的节点中，深度最大的那个节点。 二、倍增法求LCALCALCA（暴力解法这里就跳过了） 1.简介 这是求LCALCALCA最常用的方法，用倍增的思想来向上“跳”。 2.核心思想 倍增法的主要思想是：任何整数都可以用二进制表示，那么从任何一个节点到其祖先的路径长度，也可以拆分为多个222的幂次方步长。我们预先计算好每个节点向上跳 2k2^k2k 步会到达哪里，查询时就能快速向上“跳”，而不需要一步一步走。 3.算法流程 * 预处理： depth[i]depth[i]depth[i]：记录每个节点 iii 的深度。 up[i][j]up[i][j]up[i][j]：这是核心的倍增表。它表示从节点 iii 开始，向上跳 2j2^j2j 步后，所到达的祖先节点。 这两个数组均可在dfsdfsdfs中通过递推实现。 depthdepthdepth就不说了，我们重点讲解upupup，注意到从 iii 点跳 2j2^j2j 步 === 先从 iii 点跳 2j−12^{j-1}2j−1 步到一个中间节点 midmidmid，再从 midmidmid 节点跳 2j−12^{j-1}2j−1 步，由此，up[i][j]=up[up[i][j−1]][j−1]up[i][j] = up[ up[i][j-1] ][j-1]up[i][j]=up[up[i][j−1]][j−1]，这样，我们可以用已经计算好的 第j−1j-1j−1 层的信息，来构建第 jjj 层的信息。 * 查询 1. 深度对齐：首先，确保两个节点 uuu 和 vvv 处于同一深度。假设 depth[u]>depth[v]depth[u] > depth[v]depth[u]>depth[v]，我们需要把 uuu 往上提。计算深度差 d=depth[u]−depth[v]d = depth[u] - depth[v]d=depth[u]−depth[v]。将深度差 ddd 看作一个二进制数，利用倍增表快速提升 uuu。 2. 检查是否同一节点： 如果此时 u=vu =vu=v，那么这个点就是LCALCALCA，直接返回。 3. 同步攀升：如果深度对齐后 uuu 和 vvv 不同，则让它们一起向上跳，从最大的步数 k=20k = 20k=20 开始尝试，向下递减，如果 up[u][k]!=up[v][k]up[u][k] != up[v][k]up[u][k]!=up[v][k]，说明这个祖先还不是公共的（还没越过LCALCALCA），我们就可以安全地将 uuu 和 vvv 同时向上跳 2k2^k2k 步，否则说明越过了LCALCALCA，不跳。 4. 经过第333步后，uuu 和 vvv 会停留在LCALCALCA的正下方的两个直接子节点上。因此，uuu 和 vvv 此时的父节点就是LCALCALCA，即 up[u][0]up[u][0]up[u][0]。 4.代码实现 * 时间复杂度：O(nlogn)O(nlogn)O(nlogn) * 空间复杂度：O(nlogn)O(nlogn)O(nlogn) OK啊，终于杀青了！打字不易，点个赞吧。 特别鸣谢@AAA混泥土批发PPL哥、@复仇者_帅童对于FLOYDFLOYDFLOYD算法的指正、@沈思邈对于一些细节的建议！

题解

可以看样例？？？ 绝对不是F12！

ACGO官方赛事公平审核规则 为保障竞赛公平性与公信力，我们对不同类型赛事采取差异化规则，其中 挑战赛 和 巅峰赛 启用重点审核与违规累计机制，欢乐赛则以轻松参与为主，不设扣分处罚。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 审核范围 挑战赛 & 巅峰赛 * 审核对象： 每次赛事 排行榜前100名选手&随机抽取N名选手的提交代码。 * 审核标准： * AI生成度过高（检测算法判定）； * 代码相似度过高（疑似抄袭、小号作弊）； * 传递或索要代码。 * 审核团队： 由 志愿者 + 老师 共同负责，确保公平公正。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 违规与处罚机制（挑战赛 & 巅峰赛） * 第1至第3次违规： 内部记录，不扣表现分，取消礼品赠送； * 第4次违规： 依据情况扣除表现分，取消对应勋章； * 第5次及后续违规：继续扣除表现分。 从巅峰赛#23起记录 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 公告机制 * 每次赛事结果公告时，仅会公布： * “本次赛事已对前100名进行审核，X位用户因违规被记录/处罚。” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 申诉机制 * 用户可在 赛后提交申诉（需提供详细解题思路）。 * 经审核确认无违规，将撤销本次记录。

我妈就是躺赢狗！！！

目录 * 第一部分：导言 * 第二部分：什么是动态数组 * 第三部分：vector数组的使用方法 * 第四部分：刷题时光 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 建议先学习SORT排序在来学VECTOR，本文会涉及到SORT排序 第一部分：导言 很多人很会用原生态数组（原生态数组如下） 但是这样子会很费空间，所以我们今天带来了一种新的动态数组——vector数组 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第二部分：什么是动态数组 在我们学习原生态数组时，我们知道，数组是要定长的（定义长度），原生态数组一旦定义，就会分配到固定空间 * 比如 这样在程序执行前已经在内存中分配好的空间，不能在程序执行过程中改变，但是在很多情况下，我们炳不知道数组的确切大小，这是可以用动态数组~ vector是C++中的STL库中的动态数组，所谓的动态数组，就是可以在使用过程中自动的扩容，变长，并不需要预先定义好大小哦~ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第三部分：VECTOR数组的使用方法 首先我们先知道VECTOR数组的导入库 然后就是学习如何定义VECTOR数组 再然后就是学习如何操作VECTOR数组 * vector的访问 很多小白可能会这样访问 但是这样子你就会喜提一个RE，hhh、 因为我们还没输入任何东西，所以数组会越界获得RE（前文说了他是动态数组） * vector的输入和删除 如果你想在vector数组是读入数据，就可以使用，push_back方法 注意，push_back是直接推进最后一个如下图 > 推入前 ———————————————————— | ———— ———— <---- ———— | |元素1号 | |元素2号| <---- |元素三号| | ———— ———— <---- ———— |———————————————————— > 推入后 ———————————————————— | ———— ———— ———— | |元素1号 | |元素2号| |元素三号| | ———— ———— ———— |———————————————————— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如果你想删除vector数组末尾（最后一个） 的数据，可以使用pop_back()方法 > 删除前 ———————————————————— | ———— ———— ———— -------> | |元素1号 | |元素2号| |元素三号| -------> | ———— ———— ———— -------> |———————————————————— > 删除后 ———————————————————— | ———— ———— | |元素1号 | |元素2号| | ———— ———— |———————————————————— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 访问元素 可以使用下标操作符 [] 或 at() 方法访问 vector 中的元素： > 但是你得确保数组里有数据，这个是VERY VERY重要的！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 清空VECTOR 如果你想清空整个vector，可以使用clear()方法 > 清除前 ———————————————————— | ———— ———— ———— | |元素1号 | |元素2号| |元素三号| | ———— ———— ———— |———————————————————— > 清除后 ———————————————————— | |（我是空的！！！！！！！！！！！！！！！！） | |———————————————————— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ BEGIN与END begin * begin：代表开的地址 * 如果你要获取开头元素时，就要多一个*，当然啦也可以数组名[0]解决 end * end以为结尾，end是vector的结尾元素的下一个位置的地址 * 所以，end - 1才是最后一个元素的地址 * 所以，* (v . end() - 1）表示输出v中的最后一个有效元素 > - 注意：在使用BEGIN和END时，一定要保证VECTOR非空！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ VECTOR的长度： 可以使用 size() 方法获取 vector 中元素的数量： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ VECTOR的排序 因为有一些人还不费sort排序，这里我就讲一下 sort排序的专用库是algorithm（记得导入） 然后就是语法sort（开始位置 ， 结尾最后一个位置） * 例如，我们想对数组中a[0]道a[8]这九个元素排序时（这是原生态数组）可以写 所以vector数组的排序就要用到begin和end ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第四部分：刷题时光 FIRST：B2089 数组逆序重存放 * 题目大意：读入一个整数n，然后输入一个给我们排序好的n个数，让我们倒序输出 * 题目思路：可以使用vector数组先读入这些数，然后逆序输出 STEP01：定义VECTOR数组 STEP02：读入数据并逆序输出 最后就是CodeCodeCode环节了 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ SECOND：B2093 查找特定的值 * 题目大意：读入n个数，查找x第一次出现的位置，如果这n个数里并不包含x的话，输出-1 * 题目思路：首先还是先读入这些数，然后使用pos变量来算位置，最后判断 STEP01 定义并读入 STEP02：随后查找X STEP03：最后判断 CodeCodeCode环节来啦！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ THIRD：B2094 不与最大数相同的数字之和 * 题目大意：在n个数中，输出不是最大数相同的数字的和 * 方法：先读入，然后再查找最大数，最后除最大数以外的数算出和 STEP01：定义并读入 STEO02：找出最大值 STEP03：求和 STEP04：输出和 CodeCodeCode环节来啦 创作不易，给一个赞吧，求求了

.

链接 涉及初中光学、电学、力学和化学 400分可拿百元大奖（不计人数），均为答案提交题

非人能做！

请先打开AC狗问他你的代码错哪了

LaTeX数学公式的常用语法讲解传送门 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Markdown是一种轻量级标记语言，用于格式化纯文本，本文为Markdown的一些常用语法讲解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 标题： 使用#符号来创建标题，1个#代表一级标题，2个#代表二级标题，以此类推，最多支持六级标题。 效果： 一级标题 二级标题 三级标题 四级标题 五级标题 六级标题 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 强调和斜体和划线： 使用*包围文本以实现斜体效果，使用**包围文本以实现加粗效果，使用~~包围文本以实现加粗划线效果。 效果： 斜体文本 加粗文本 划线文本 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 链接： 创建链接使用[],()。[]中放置链接文字，()中放置链接地址。 效果： 点击这里百度一下 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图片： 插入图片使用!,[],()。[]中放置替代文字，()中放置图片链接。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 列表： 无序列表使用-,+,*开头，有序列表使用数字 +.。 效果： * 无序列表项 * 无序列表项 1. 有序列表项 2. 有序列表项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 引用： 使用>来创建引用块，可以引用叠引用。 效果： > 这是引用的内容 > > > 这也是引用的内容 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码块： 用三个反引号`包围代码块，后面可以跟着一个语言名称来指定代码块的语言，以便语法高亮。 记得去掉\。 效果： 一个反引号`可以作为单行代码块。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 水平分隔线： 使用三个或更多连续的*来创建水平线。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 表格： 表格由表头和表格内容组成，使用|,-来分隔不同的行列，下面是一个简单的表格示例： 使用|来分隔每一列，而使用-在表头下创建分隔线。表头是必需的，它定义了每一列的标题。 效果： 标题1 标题2 标题3 内容1 内容2 内容3 内容4 内容5 内容6 希望表格的内容居中或靠右对齐，可以使用:来指定对齐方式，例如： 输出结果如下： ---左对齐--- ---居中对齐--- ---右对齐--- 内容1 内容2 内容3 内容4 内容5 内容6 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 脚注： 在文本中需要添加脚注的位置，使用[^]来标记脚注的引用标记，方括号内可以填写任何标识符，通常是数字例如[^1]。 在文档的末尾，添加一个相匹配的脚注内容，使用[^]: 内容的形式来定义脚注内容。例如[^1]: 这是脚注的内容。 下面是一个示例： 结果： 这是一个示例[1]，在文末可以看到脚注的解释。 脚注会显示在全文的最下面，请到最底部查看脚注。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 数学公式： 单个$用于表示行内数学公式或数学表达式，用于排版数学符号、方程式、上下标、分数等数学内容，他的使用通常与LaTeX\LaTeX{}LATE X数学语法相对应，因为Markdown支持一些LaTeX\LaTeX{}LATE X的数学语法，例如： 效果： y=mx+by = mx + by=mx+b 两个$用于表示多行数学公式或数学表达式，例如： 效果： n!k!(n−k)!=(nk)\frac{n!}{k!(n-k)!} = \binom{n}{k} k!(n−k)!n! =(kn ) 数学公式里，^,_用于表示上标与下标，后面可以用括号包括进一大串数字与字母 效果： ai+j+bja^{i+j}+b_{j}ai+j+bj ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以上是Markdown的常用语法讲解，欢迎评论讨论。 评论区用不了Markdown，题目，团队介绍能用，忘记说了赶紧补充 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 这是脚注的内容，用于解释示例的含义。 ↩︎

TARJAN 连通性问题学习笔记 可能更好的阅读体验 前言 > 声明：跳过本部分的阅读并不影响您学习算法。 其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。 大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。 于是我就决定先放一放。 几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。 记录 > 如果您还能看到这段话，代表笔者还打算继续更新。 > 目前计划：更新强连通分量例题。 * upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。 强连通分量 概念理解 * 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，则称 uuu 和 vvv 是强连通的。 * 强连通图：如果一个有向图 GGG 中，所有节点互相强连通，则称 GGG 是强连通图。 * 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图 GGG，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。 其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。 以上图举例，我们认为 {a,b,c,d,e}\{a,b,c,d,e\}{a,b,c,d,e} 属于同一个 SCC，而并非两个 SCC。 算法讲解 让我们先画一个图。 为了引出算法，让我们再画一个 DFS 搜索树。 由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。 假设按照 {a,b,d,c,f,e}\{a,b,d,c,f,e\}{a,b,d,c,f,e} 的顺序进行 DFS。我们讲所有指向未被搜索的边叫做树边（如图中黑色边，且必须由父亲指向儿子），而指向已被搜索的边叫做非树边（如图中黄色边）。 好，接下来让我们直接推出一个定理。 * 不存在两个节点 uuu 和 vvv，满足两点不为祖孙关系，且在 uuu 和 vvv 的子树中有非树边互相连接。换句话说，如果在 uuu 的子树中有一个点由一条非树边指向 vvv 的子树的某个点，那么 vvv 的子树中就一定没有一个点由一条非树边指向 uuu 的子树的某个点。 证明： > 因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。 为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。 一般用代码这么实现： 然后再定义一个 SCC 中的根为其中 dfn 最小的节点。 让我们再引出一个定理： * 一个 SCC 中的所有点必然出现在其的根的子树中。 证明： > 使用反证法。 > 如果一个 SCC 中的点 xxx 不在根的子树中，而是根的祖先，那么 xxx 的 dfn 必然小于 SCC 的根，矛盾。 > 如果一个 SCC 中的点 xxx 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。 > 故证毕。 至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。 那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。 只要当存在一个节点 xxx 满足 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么它必然是 SCC 的根。 上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。 或许你会觉得很晕，让我们回到最开始的图来举例吧。 在上述图中，SCC 有三个，分别为 {f},{e},{a,b,c,d}\{f\},\{e\},\{a,b,c,d\}{f},{e},{a,b,c,d}；其中，按照 {a,b,c,d,e,f}\{a,b,c,d,e,f\}{a,b,c,d,e,f} 的顺序，dfn 值分别为 {1,2,4,3,6,5}\{1,2,4,3,6,5\}{1,2,4,3,6,5}，low 值分别为 {1,1,1,1,6,5}\{1,1,1,1,6,5\}{1,1,1,1,6,5}。正好符合我们的“猜测”。 让我们看看 low 的更新步骤。 * 如果节点 uuu 可以通过一条边访问一个未被访问的节点 vvv，那么该边为树边。我们需要先搜索节点 vvv，然后更新 lowu=min⁡{lowu,lowv}\text{low}_u=\min\{\text{low}_u,\text{low}_v\}lowu =min{lowu ,lowv }，因为树边并不影响我们对于“经过最多一条非树边”的限制。 * 如果节点 uuu 可以通过一条边访问自己的祖先 vvv，那么该边为非树边。我们更新 lowu=min⁡{lowu,dfnv}\text{low}_u=\min\{\text{low}_u,\text{dfn}_v\}lowu =min{lowu ,dfnv }。注意必须得用 dfnv\text{dfn}_vdfnv 更新，因为已经消耗了“最多一条非树边”的限制。 * 如果节点 u,vu,vu,v 没有祖孙关系，那么什么也不做。 然后是回溯，我们需要再引入一个栈辅助。每个节点 xxx 在被访问时就先压栈，当其把所有边都访问完之后开始回溯。判断如果 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么该节点必然为 SCC 的根，我们只需一直弹栈直至弹出节点 xxx，中间的所有节点均为同一个 SCC。 怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点 vvv，一定会在此之前先被弹栈。因为如果 vvv 与 xxx 不强连通，那么必然是 lowv\text{low}_vlowv 为一个大于 dfnx\text{dfn}_xdfnx ，小于等于 dfnv\text{dfn}_vdfnv 的数（因为节点 xxx 是一定可以通过树边直达 vvv 的），既然时间戳比根 xxx 晚，所以就能很轻易的得出时间戳为 lowv\text{low}_vlowv 的节点会在 xxx 回溯之前将 vvv 弹栈。 上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。 为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。 参考资料 《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。