比题解1更简单易懂的DFS

1. 前言：一开始我不明白什么时候输出infinity，然后去看了题解1的代码，发现使用了dfs+回溯，其中的逻辑并不是特别容易理解。但是通过阅读那个题解我明白了什么时候需要输出infinity，下面讲解思路
2. 输出infinity的条件：相信很多卡在这道题的选手都是对这一点有困扰，这里我举一个浅显的例子。假设，通过abbbb这样的选择我们可以从0到达终点，但如果同时存在aa这样的选择可以使我们从0到达0，那么最终符合要求的字符串可以有无限多个，其正则式为(aa)*abbbb,且每多一个aa其字典序都严格变小，所以这时候需要输出infinity
3. 知道了infinity的判断思路后，我们具体要怎么实现呢?很简单，因为DFS时我们先找走a[i]步的情况来使得结果的字典序尽可能小，所以如果存在这样的环路，那么最终的访问序列中一定有某个结点的访问次数大于1，我们设置一个vis[N]数组记录DFS过程中结点的访问次数即可。注意在最终的判断时只需要判断存在于答案访问序列中的点，而不是DFS过程中所有的点
4. ac代码

#include <bits/stdc++.h>
using namespace  std;
typedef long long ll;
const int N=1e5+5;
int n,a[N],b[N];
int flag,flag2,vis[N];
char ans[N];
char ans2[N];
void dfs(int x,int dep){

	if(flag) return ;
	if(vis[x]>0) {vis[x]++;return;}
	else vis[x]++;
	if(x==n-1) {
		for(int i=0;i<dep;i++)
			ans2[i]=ans[i];
		flag=1;
		return ;
	}
	if(x+a[x]>0&&x+a[x]<n){
		ans[dep]='a';
		dfs(x+a[x],dep+1);
	}
	if(x+b[x]>0&&x+b[x]<n){
		ans[dep]='b';
		dfs(x+b[x],dep+1);
	}
}
void solve(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  dfs(0,0);
  if(flag) {
	int tmp=0;
	for(int i=0;i<strlen(ans2);i++){

		if(vis[tmp]>1) flag2=1;
		if(ans2[i]=='a') tmp+=a[tmp];
		else tmp+=b[tmp];
	}
	if(flag2) cout<<"Infinity!"<<endl;
	else cout<<ans2<<endl;
  }
  else cout<<"No solution!"<<endl;

}
int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	//cin>>T;
	while(T--) solve();
}