#1519. 虫洞
虫洞
题目背景
在遥远的未来,人类文明迈入星际纪元。虫洞网络的建立彻底改变了宇宙旅行的方式——每一个虫洞都如同一道时空之门,将穿越者瞬间传送到另一个指定位置。作为星际探索者,你正驾驶飞船穿梭于这片神秘的虫洞网络之中。
然而,并非所有路径都通向自由。某些虫洞之间会形成封闭的循环,一旦陷入,便再也无法抵达其他区域。幸运的是,你拥有有限的“跃迁权限”,可以在关键时刻主动跳转至任意虫洞前,打破循环的束缚。
现在,挑战摆在你面前:能否在跃迁次数耗尽前,恰好访问每一个虫洞一次?
题目描述
已知存在 n 个虫洞,编号为 1 到 n。每个虫洞 i 都会将你自动传送到虫洞 a [i] 前(保证 a [1],a [2],…,a [n] 是 1 到 n 的一个排列)。
输入格式
第一行:两个整数 n 和 k(1 ≤ n ≤ 2×10^5,0 ≤ k ≤ 10),分别表示虫洞的数量和跃迁机会的次数; 第二行:n 个整数 a [1],a [2],…,a [n](为 1 到 n 的排列),表示第 i 个虫洞会将你传送到第 a [i] 个虫洞前。 (排列:[1,2,3]是3的一个排列,[2,3,1]也是3的一个排列,[1,3,4]不是3的排列,因为4不在1到3之内;[1,3,3]也不是3的排列,因为3出现了两次)
输出格式
输出 YES 或 NO,表示能否在限定跃迁次数内完成目标
样例
5 1
5 3 2 1 4
YES
样例解释
起始于 1 号虫洞前。 穿过 1 → 访问 1,传送到 5 穿过 5 → 访问 5,传送到 4 穿过 4 → 访问 4,传送到 1(1 已访问,若继续将重复) 此时已访问虫洞 {1, 5, 4},剩余 {2, 3} 尚未访问。
使用 1 次跃迁,跳至 2 号虫洞前 穿过 2 → 访问 2,传送到 3 穿过 3 → 访问 3,传送到 2(已访问,停止) 共访问全部 5 个虫洞,仅用 1 次跃迁,满足条件,故输出 YES。