基环树找环

abc167_d Teleporter

#include<bits/stdc++.h>
#define pt printf(">>>")
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
vector<ll> G[N];
map<ll,bool> loop;
ll n,a[N],k;
ll f[N],dfn[N],tot;
void getloop(ll u,ll fa){
	dfn[u]=++tot,f[u]=fa;
	for(auto v:G[u]){
		if(v==fa)continue;
		if(dfn[v]>dfn[u]){
			loop[v]=true;
			while(v!=u)loop[v=f[v]]=true;
		}else if(!dfn[v])getloop(v,u);
	}
}
int main(){
	cin >> n >> k;
	for(ll i=1;i<=n;i++){
		cin >> a[i];
		G[a[i]].push_back(i);
		G[i].push_back(a[i]);
	}
	getloop(1,0);
	if(loop.size()==0)k=min(k,n);
	else if(k>n)k=n+(k-n)%(loop.size());
	ll now=1;
	for(ll i=1;i<=k;i++)now=a[now];
	cout << now;
	return 0;
}