1. 题目描述

1.1. Limit

Time Limit: 2000 ms

Memory Limit: 1024 MB

1.2. Problem Description

The Kingdom of Takahashi has NNN towns, numbered 111 through NNN.

There is one teleporter in each town. The teleporter in Town iii (1≤i≤N)(1 \leq i \leq N)(1≤i≤N) sends you to Town AiA_iAi.

Takahashi, the king, loves the positive integer KKK. The selfish king wonders what town he will be in if he starts at Town 111 and uses a teleporter exactly KKK times from there.

Help the king by writing a program that answers this question.

1.3. Input

NNN KKK
A1<mtext>   </mtext>A2<mtext>   </mtext>…<mtext>   </mtext>ANA_1\ A_2\ \dots \ A_NA1 A2 … AN

1.4. Constraints

2≤N≤2×1052 \leq N \leq 2 \times 10^52≤N≤2×105

1≤Ai≤N1 \leq A_i \leq N1≤Ai≤N

1≤K≤10181 \leq K \leq 10^{18}1≤K≤1018

1.5. Output

Print the integer representing the town the king will be in if he starts at Town 111 and uses a teleporter exactly KKK times from there.

1.6. Sample Input 1 

4 5 3 2 4 1

1.7. Sample Output 1 

4

If we start at Town 111 and use the teleporter 5 times, our travel will be as follows: 1→3→4→1→3→41 \to 3 \to 4 \to 1 \to 3 \to 41→3→4→1→3→4.

1.8. Sample Input 2 

6 727202214173249351 6 5 2 5 3 2

1.9. Sample Output 2 

2

1.10. Source

AtCoder 4804 Teleporter

2. 解读

将所有路径使用邻接表进行存储，然后对路径依次进行遍历，将遍历过的节点存储在栈 StackStackStack中，找出图中的环路。

在节点入栈前，判断其是否在栈中，若在，则该节点首次出现的位置到栈顶位置之间的节点所连成的边即为我们要找的环路 CCC，求出环路长度 SSS。

判断 游走次数 KKK 是否大于图的起点 Q0Q_0Q0 到环路起点 W0W_0W0 的距离 length=Q0−W0length = Q_0 - W_0length=Q0−W0。

若 K>lengthK > lengthK>length，则输出 StackStackStack 中从 000 开始计数第 Q0+(K−W0)%SQ_0 + (K - W_0) \% SQ0+(K−W0)%S 个元素。

若 K≤lengthK \le lengthK≤length，则输出 StackStackStack 中从 000 开始计数第 KKK 个元素。

3. 代码 

#include <iostream> #include <string.h> #include <vector> using namespace std; const int NUM = 2 * 10e5 + 1; // 存储 long long list[NUM]; // 标志访问 bool visit[NUM]; // 栈存储访问路径 vector<long long> vec; int main() { // test case long long n, k; scanf("%lld %lld", &n, &k); // 初始化 memset(list, 0, sizeof(list)); memset(visit, 0, sizeof(visit)); // 输入 for (long long i = 0; i < n; i++) { scanf("%lld", &list[i]); } // 初始化 long long buffer = 1; // 计算 for (int i = 0; i < n; i++) { // 标志访问 visit[buffer] = 1; // 节点入栈 vec.push_back(buffer); // 获取下一个节点 buffer = list[buffer - 1]; // 若形成环路 if (visit[buffer] == 1) { break; } } // 在栈中找出环路开始位置 auto it = find(vec.begin(), vec.end(), buffer); // 环路长度 long long cycleLength = vec.end() - it; // 环路开始前的栈深度 long long stackLength = it - vec.begin(); // 计算从环路起点开始的位移 long long posMark; if (k > stackLength) { // 若存在环路 posMark = (k - stackLength) % cycleLength; } else { // 若不存在环路 posMark = (k - stackLength); } // 输出 printf("%lld\n", vec[stackLength + posMark]); }

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。