【2022省选模拟】传染——tarjan缩点、点分治优化建图

此题不提供链接
题目描述

题解
这题出得太好了，算是把点分治考透了。
这道题实质上就是要求一个强连通分量缩点后入度为0的分量的数目的问题。每个点向

r

i

r_i

ri​ 距离内的点连一条有向边，那么对于这个有向图，同一个强连通分量内的点肯定只需要动随便一个就能全部传染，所以进行缩点之后，就只有那些入度为0的连通分量需要被操作恰好一次。
现在的问题是，每个点向外连出的边太多了，总边数可能达到

n

2

【2022省选模拟】传染——tarjan缩点、点分治优化建图最先出现在Python成神之路。