对Tarjan的算法理解有点要求的题，之前看了一下思路，敲了一下结果没过，照着博客改动了一下但并没有搞懂，今天补上。 题意： 给你一个有向图，若干询问，询问为从 s 到 t 的最小字典序路径中，第 k 个点是哪个点。 思路： 首先询问很多，有$4\times10^5$个询问，直接一个一个找肯定是不行的。 但是值得注意的是，点数比较少，只有$3000$个，假如我们固定起点，遍历全图来获得路径，在遍历的同时，对每一个点来记录答案。理想复杂度为$O(N^2)$，时间上满足条件。 一个问题是如何保证字典序最小，emmmm 用vector记录整张图，对于每个点的边进行排序，因为每个点访问一次，解决之。 这题还有一个合理的大坑，如果在遍历的时候，在之前已经出现了一个环，那么之后的所有点就都不会被访问。 当然你不能在找到一个环后，后面的点就不再遍历，…
LCA 好题！ 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质： 深度优先搜索时的向下局部性。自己乱取得，蛤蛤蛤 题意： 给你一棵树，每个节点有一个权值。给你很多个询问，每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路： 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况： 1. u -> lca 的最大差值 2. lca -> v 的最大差值 3. lca -> v 的最大值 – u -> lca 的最小值 考虑dp维护这四个值。 因为运用Tarjan算法的时候，基于dfs，在你的眼里，当前节点就是向下整棵树的根节点，你完全不会去考虑往上的节点。 所以你现在使用的四个值，刚好是你当前节点的孩子节点的最优值。 基于这个事实，…
好烦，感觉自己的图论知识都有了，但是一旦写起来还是非常欠缺…… 什么时候我才能踩完所有的坑，成就大佬之路呢…… 今天多校的第二道签到题…… 是的，签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错…… 今天错的地方是没有去重，还像条疯狗一样跑去BC官方博客理论了…… 在这里先道个歉…… 但是题解的确没写清楚 题意： 给你一个有向图，有环，无重边，无自环。 问你是否存在两个不联通的点。 思路： 拿到题的第一思路，拓扑排序，有环就缩点呗！ 然后开始疯狂WA…… 思路没错，但是在缩点后没有去重，导致缩点后一条边的出度增加，拓扑排序失败…… 好烦……讲道理缩点+拓扑，虽然简单，但也没有沦落到这种比赛的签到题上…… 原因就是数据很小，允许 ( O ( n^2 ) )解题…… 可能因为图论学傻了，没想到也不愿意用暴力做…… 暴力的方法是，枚举每一个点，记录它可以达到的点，构成一个二维矩阵，然后遍历一下矩阵，看是否存在相互不可达的点即可。 虽然暴力在我眼里有点不齿，但是优雅的暴力还是非常值得认可的。…
由已知婚姻匹配求出所有可出轨匹配。
因为稳定婚姻问题中的匹配都是完美匹配，因此也可以换一种说法，已知一个完美匹配，求出所有完美匹配。
这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少，感觉都是套路……
求稳定婚姻就是模拟的板子，判定和所有出轨匹配就是tarjan缩点……
尽管如此，但还是不得不学啊……
题意：
一个国王有很多个儿子，这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来，刚好儿子和女孩的数量相同。所以只能一夫一妻了。
国王要大臣给个可行方案，大臣给了。国王又要所有可行方案。大臣就烧脑子了。
儿子最多2000个……囧……厉害厉害
思路：
其实方法的话……基本还是和稳定婚姻的判定是一样的。稳定婚姻判定点这里
在求出所有强联通分量之后，找出男性的所有可婚配配偶 和 与他在同一个强联通分量的女性的交集。
从小到大输出这个交集就是我们要求的答案。
AC Code ( 时间略长……
#include
稳定婚姻的判定问题。 老实说，写了几题后发现稳定婚姻问题几乎都是板子题……囧…… 而且我作为入门题写的那道题好歹还披了一件外套，有几道完完全全的裸题写得我是非常的空虚…… 回到这道题，这道题应该算是稳定婚姻判定的裸题了。 假如我们再次无脑套模板，复杂度还是在( O(n^2) )左右。 我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻，那就是不稳定的。 从而，对于一个已知的婚姻匹配，如果存在一对夫妻离婚，但不会对其他夫妻造成任何影响，那么这组婚姻匹配就是稳定的。 稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。 一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图，对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配，他们被染色的数量超过 ( 1 ) 是什么颜色呢？？ 那这个婚姻匹配就是不稳定的。 复杂度为Tarjan的复杂度，估计在( O( n ) ) 左右。 题意： 先给你一组婚姻匹配，再给你几组可出轨匹配，问你对于每一对夫妻，他们的匹配是否安全。 思路： 裸题啦，裸题，看了我上面的陈述就知道该怎么写了。 A…
本来以为是一道好题……
没想到xjb被我水过去了……
题目看不大懂去找题解看题意，都说什么LCA，醉了……真的不喜欢数据弱的题目。
题意：
给你一棵生成树，再多给你几条边，要你只能删除一条生成树的边的同时，最少删掉多少条边才能使得整张图图不联通。
思路：
一个很显然的规律就是，找到生成树上度数为1的点，再比较其他度数和即可……
这里有个漏洞，就是可以在删掉一条生成树上的边就可以分割整张图，简单说，就是桥……
不是很懂他们LCA的思路，水过了就不想思考了。我倒是觉得，直接tarjan缩点预处理一下，再特判一下缩点后的点数即可。
AC Code
#include