Atcoder Beginner Contest 445 - C

C - Sugoroku Destination

题目大意

有 $n$ 个格子，第 $i$ 格子上有整数 $a_i$ ，对于每个单元格 $s$ ，在格子中放入一个棋子，然后执行 $10^{100}$ 次：将棋子移动到单元格 $A_s$ 。最后输出棋子编号

思路

很显然 $10^{100}$ 过大，无法直接模拟，因为 $10^{100}$ 明显超过 $n$ ，所以最后必定进入环，本质其实是找环的终点

实现

写一个简单的递归函数

int dfs(int i){
	if(a[i]==i)return i;
	return dfs(a[i]);
}

但是会超时，加个记忆化

int dfs(int i){
	if(vis[i])return vis[i];
	if(a[i]==i)return vis[i]=i;
	return vis[i]=dfs(a[i]);
}

搞定！

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[500010];
int vis[500010];
int dfs(int i){
	if(vis[i])return vis[i];
	if(a[i]==i)return vis[i]=i;
	return vis[i]=dfs(a[i]);
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cout<<dfs(i)<<"\n";
	}
	return 0;
}

时间复杂度： $O(n)$

AC记录

再见