警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

Tarjan 第一轮复习 - Tarjan

RT.

算法流程

  • \(dfn\)\(low\)

    • 如果 \(nx\) 没被访问过,那么 \(low_x=\min(low_x,low_{nx})\)

    • 如果 \(nx\) 被访问过且还在栈中,那么 \(low_x=\min(low_x,dfn_{nx})\)

  • SCC:

    如果 \(dfn_x=low_x\),那么 \(x\) 是它所在的 SCC 中 \(dfn\) 最小的点。

    此时可以不断弹栈,直到弹出 \(x\)。弹出的所有点均属于 \(x\) 所在的 SCC。

    缩点:\((x\to y)\Rightarrow(col_x\to col_y)\)

  • 割边 / 桥:

    如果存在 \(nx\in son_x\)\(dfn_x<low_{nx}\),那么 \(x\leftrightarrow nx\) 是桥。

  • 割点:

    如果 \(x\) 不是根,且存在 \(nx\in son_x\)\(dfn_x\le low_{nx}\),那么 \(x\) 是割点。

    如果 \(x\) 是根,那么当且仅当存在至少两个 \(nx\in son_x\) 满足上述条件。

  • e-DCC:

    e-DCC 是一个满足图中没有桥的,极大的子图。

    删去所有的桥后,每一个连通块构成一个 e-DCC。

  • v-DCC:

    v-DCC 是一个满足图中没有割点的,极大的子图。

    咕咕咕。

  • (广义)圆方树(block forest):

    定义不管了,看图吧:

    给每一个 v-DCC 开一个方点,把 v-DCC 中的每一个点连向这个方点,连成一个菊花。

    孤立点具体情况具体分析。

  • LCA:

    待填

题目

裸的 Tarjan 题太少了,所以写点圆方树算了。找到了好题再补吧

圆方树

P4606 战略游戏

题意

给一张图,每次查询一个点集 \(S\),求包含点集 \(S\) 的最小连通块中的割点数。

数据范围待填。

解法

注意到图的割点数就是圆方树上的圆点数。所以建出圆方树,然后就变成了求包含点集 \(\mathbf S\) 的最小连通块的割点数

那么令 \(|S|=k\)\(\operatorname{dis}(x,y)\)\(x\leftrightarrow y\) 的圆点数,那么答案就是

\[\frac{\operatorname{dis}(S_1,S_2)+\cdots+\operatorname{dis}(S_{k-1}+S_k)+\operatorname{dis}(S_1,S_k)}2-k\]

然后算出来就好了。

注意特判 \(\operatorname{LCA}(S_1,S_k)=1\) 的情况。

代码

CF487E Tourists

题意

给一张带点权的图,支持查询两点间所有简单路径上最小点权的最小值,修改一个点的点权。

数据范围待填。

解法

如果没有修改,那么直接在方点上维护整个 v-DCC 的最小值,圆点上放当前点的权值,然后在圆方树上求链上最小值即可。

但是如果有修改,可以用菊花图卡到单次修改复杂度 \(O(n)\)

考虑随便定一个根(如 \(1\)),在方点上维护它儿子的权值最小值。那么每次修改时,只要修改它自身和它父亲就好了。如果被修改的点是根则不需要修改它的父亲。

查询的时候直接查询链上最小值。注意,如果查询的两个点当根为 \(1\) 时的 LCA 是方点,那么答案需要对 LCA 的父亲取 min。

代码