B003 找循环节 建图 ABC167D
模板题: ABC167D 不需要建图模板题：AWC Beta0025D 需要建函数图
这道题目需要先建图。建一个函数图 nxt 数组，建完后寻找循环节。这里重点讲解如何寻找循环节。
从起点出发在经过一条链后才可能进入到环中，所以这个图结构也可以称为基环树或 \(\rho\) 形图 。
关键是找到环的两个信息：尾巴长度和环大小。
具体算法解题流程为：
[*] 确定核心变量
[*]vised ：记录每个节点第一次被访问到时是第几步，可以使用数组或哈希表。
[*]order：按照访问顺序，把经过的节点放进列表，即 \(\rho\) 形图的轨迹。
[*]pos：当前所在节点，初始为题目给出的初始节点 S 。
[*]step：即当前走过的总步数。
vised = [-1] * (n + 1)
pos = s
step = 0
order = []
[*] 模拟行走
while vised != -1:
vised = step
order.append(pos)
pos = nxt
step += 1
[*] 计算环的信息
由第 \(2\) 步可知，最后的 vised 就是环的起点。所以尾巴大小 tail_size 为 vised 。
那环的大小 cycle_size 就是总长度减去尾巴大小了。
tail_size = vised
cycle_size = step - tail_size
[*] 计算 \(Q\) 步后的节点
[*] Q < tail_size
要求的步数比尾巴还小，没有进入环的部分，直接在 order 里找第 \(Q\) 个即可。
[*] Q >= tail_size
先加上尾巴的大小，然后对 Q - tail_size 进行取模，模数就是环的大小。
if q < tail_size:
ans = order
else:
ans = order
经过while循环后获得的环信息
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]