Posts tagged with Tarjan


对Tarjan的算法理解有点要求的题,之前看了一下思路,敲了一下结果没过,照着博客改动了一下但并没有搞懂,今天补上。 题意: 给你一个有向图,若干询问,询问为从 s 到 t 的最小字典序路径中,第 k 个点是哪个点。 思路: 首先询问很多,有$4\times10^5$个询问,直接一个一个找肯定是不行的。 但是值得注意的是,…

LCA 好题! 这道题我暂时只知道用Tarjan的解法。 Tarjan解法完美地运用了Tarjan的核心原理与性质: 深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤 题意: 给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。 思路: 首先考虑分治。设树链 u -> lca -> v 答案无非只有三种情况: u…

好烦,感觉自己的图论知识都有了,但是一旦写起来还是非常欠缺…… 什么时候我才能踩完所有的坑,成就大佬之路呢…… 今天多校的第二道签到题…… 是的,签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错…… 今天错的地方是没有去重,还像条疯狗一样跑去BC官方博客理论了…… 在这里先道个歉…… 但是题解的确没写清楚 题意: 给你一个有向图,有环,无重边,无自环。 问你是否存在两个不联通的点。 思路: 拿到题的第一思路,拓扑排序,有环就缩点呗! 然后开始疯狂WA……

由已知婚姻匹配求出所有可出轨匹配。 因为稳定婚姻问题中的匹配都是完美匹配,因此也可以换一种说法,已知一个完美匹配,求出所有完美匹配。 这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少,感觉都是套路…… 求稳定婚姻就是模拟的板子,判定和所有出轨匹配就是tarjan缩点…… 尽管如此,但还是不得不学啊…… 题意: 一个国王有很多个儿子,这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来,刚好儿子和女孩的数量相同。所以只能一夫一妻了。 国王要大臣给个可行方案,大臣给了。国王又要所有可行方案。大臣就烧脑子了。 儿子最多2000个……囧……厉害厉害…

稳定婚姻的判定问题。 老实说,写了几题后发现稳定婚姻问题几乎都是板子题……囧…… 而且我作为入门题写的那道题好歹还披了一件外套,有几道完完全全的裸题写得我是非常的空虚…… 回到这道题,这道题应该算是稳定婚姻判定的裸题了。 假如我们再次无脑套模板,复杂度还是在( O(n^2) )左右。 我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻,那就是不稳定的。 从而,对于一个已知的婚姻匹配,如果存在一对夫妻离婚,但不会对其他夫妻造成任何影响,那么这组婚姻匹配就是稳定的。 稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。 一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图,…