B003 找循环节 建图 ABC167D

模板题: ABC167D 不需要建图
模板题：AWC Beta0025D 需要建函数图
这道题目需要先建图。建一个函数图 nxt 数组，建完后寻找循环节。这里重点讲解如何寻找循环节。
从起点出发在经过一条链后才可能进入到环中，所以这个图结构也可以称为基环树或 \(\rho\) 形图 。
关键是找到环的两个信息：尾巴长度和环大小。
具体算法解题流程为：

• 确定核心变量
  
  
  
  • vised ：记录每个节点第一次被访问到时是第几步，可以使用数组或哈希表。
    
  • order：按照访问顺序，把经过的节点放进列表，即 \(\rho\) 形图的轨迹。
    
  • pos：当前所在节点，初始为题目给出的初始节点 S 。
    
  • step：即当前走过的总步数。
    
  1. vised = [-1] * (n + 1)
  2. pos = s
  3. step = 0
  4. order = []

  复制代码
  
  
• 模拟行走
  
  1. while vised[pos] != -1:  
  2.     vised[pos] = step
  3.     order.append(pos)
  4.     pos = nxt[pos]
  5.     step += 1

  复制代码
  
  
• 计算环的信息
  由第 \(2\) 步可知，最后的 vised[pos] 就是环的起点。所以尾巴大小 tail_size 为 vised[pos] 。
  那环的大小 cycle_size 就是总长度减去尾巴大小了。
  
  1. tail_size = vised[pos]
  2. cycle_size = step - tail_size

  复制代码
  
  
• 计算 \(Q\) 步后的节点
  
  
  
  • Q < tail_size
    要求的步数比尾巴还小，没有进入环的部分，直接在 order 里找第 \(Q\) 个即可。
    
    
  • Q >= tail_size
    先加上尾巴的大小，然后对 Q - tail_size 进行取模，模数就是环的大小。
    
    
  1. if q < tail_size:
  2.     ans = order[q]
  3. else:
  4.     ans = order[tail_size + (q - tail_size) % cycle_size]

  复制代码
  
  

      

     经过while循环后获得的环信息
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！