Bobs Portal Travel

    1#include <bits/stdc++.h>
    2using namespace std;
    3#define int long long
    4vector<int> cycle;
    5bool dfs(int cur, vector<vector<int>> &adj, vector<int> &color, vector<int> &parent, vector<int> &depth){ 
    6    //0 = not visited, 1 = visiting, 2 = visited
    7    color[cur] = 1;
    8    for(int nxt : adj[cur]){
    9        if(color[nxt] == 0){
    10            parent[nxt] = cur;
    11            depth[nxt] = depth[cur] + 1;
    12            if(dfs(nxt, adj, color, parent, depth)) return true; // found cycle already
    13        } else if(color[nxt] == 1){;
    14            int x = cur;
    15            cycle.push_back(nxt);
    16            while(x != nxt){
    17                cycle.push_back(x);
    18                x = parent[x];
    19            }
    20            reverse(cycle.begin(), cycle.end());
    21            return true;
    22        }
    23    }
    24    color[cur] = 2;
    25    return false;
    26}
    27signed main(){
    28    ios::sync_with_stdio(0); cin.tie(0);
    29    int n, k; cin >> n >> k;
    30    vector<vector<int>> adj(n + 1);
    31    for(int i = 1; i <= n; i++){
    32        int c; cin >> c;
    33        adj[i].push_back(c);
    34    }
    35    vector<int> color(n + 1, 0), parent(n + 1, -1), depth(n + 1, 0);
    36    // solve with colouring dfs
    37    dfs(1, adj, color, parent, depth); 
    38    int step = 0, entry = -1; // step from one to first cycle node from that path
    39    queue<int> q;
    40    q.push(1);
    41    vector<int> dist(n + 1, INT_MAX);
    42    vector<bool> in_cycle(n + 1, 0);
    43    for(int v : cycle) in_cycle[v] = 1;
    44    dist[1] = 0;
    45    while(!q.empty()){
    46        int cur = q.front(); q.pop();
    47        if(in_cycle[cur]){
    48            step = dist[cur];
    49            entry = cur;
    50            break;
    51        }
    52        for(int nxt : adj[cur]){
    53            if(dist[cur] + 1 < dist[nxt]){
    54                dist[nxt] = dist[cur] + 1;
    55                q.push(nxt);
    56            }
    57        }
    58    }
    59    if(k < step){
    60        int cur = 1;
    61        while(k--){
    62            cur = adj[cur][0];
    63        }
    64        cout << cur << '\n';
    65        return 0;
    66    }
    67    int remain = (k - step) % cycle.size();
    68    int pos = find(cycle.begin(), cycle.end(), entry) - cycle.begin();
    69    int ans = cycle[(pos + remain) % cycle.size()];
    70    cout << ans << '\n';
    71    return 0;
    72}