B003 找循环节 建图 ABC167D

模板题: ABC167D 不需要建图
模板题：AWC Beta0025D 需要建函数图

这道题目需要先建图。建一个函数图 nxt 数组，建完后寻找循环节。这里重点讲解如何寻找循环节。

从起点出发在经过一条链后才可能进入到环中，所以这个图结构也可以称为基环树或 \(\rho\) 形图 。

关键是找到环的两个信息：尾巴长度和环大小。

具体算法解题流程为：

1. 确定核心变量

   • vised ：记录每个节点第一次被访问到时是第几步，可以使用数组或哈希表。
   • order：按照访问顺序，把经过的节点放进列表，即 \(\rho\) 形图的轨迹。
   • pos：当前所在节点，初始为题目给出的初始节点 S 。
   • step：即当前走过的总步数。

   vised = [-1] * (n + 1)
   pos = s
   step = 0
   order = []
   

2. 模拟行走

   while vised[pos] != -1:  vised[pos] = steporder.append(pos)pos = nxt[pos]step += 1
   

3. 计算环的信息

   由第 \(2\) 步可知，最后的 vised[pos] 就是环的起点。所以尾巴大小 tail_size 为 vised[pos] 。

   那环的大小 cycle_size 就是总长度减去尾巴大小了。

   tail_size = vised[pos]
   cycle_size = step - tail_size
   

4. 计算 \(Q\) 步后的节点

   1. Q < tail_size

      要求的步数比尾巴还小，没有进入环的部分，直接在 order 里找第 \(Q\) 个即可。

   2. Q >= tail_size

      先加上尾巴的大小，然后对 Q - tail_size 进行取模，模数就是环的大小。

   if q < tail_size:ans = order[q]
   else:ans = order[tail_size + (q - tail_size) % cycle_size]
   

经过while循环后获得的环信息